HZNUOJ

最短路

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:106     AC:17     Score:100.00

Description

$ZC$ 家所在的小区住着很多学妹,为了方便和学妹们联络感情,$ZC$ 大佬决定在原有的道路上,再建一些道路。由于$ZC$ 太强了,它可以搭建以下两种道路:

$1$ $u$ $L$ $R$ $w$:对于区间 $L,R$ 中的每一个位置 $i$,搭建一条 $u$ -> $i$ 的长度为 $w$ 道路。

$2$ $L$ $R$ $u$ $w$:对于区间 $L,R$ 中的每一个位置 $i$,搭建一条 $i$ -> $u$ 的长度为 $w$ 道路。

已知 $ZC$ 的家在 $1$ 号位置,请问搭建道路后,$ZC$ 到每个学妹家的最短距离是多少?


Input

第一行包含两个正整数 $n$ , $m$,分别表示位置总数和原有的道路数。$(1 \leq n \leq 10^5,1 \leq m \leq 5 \times 10^4)$

接下来 $m$ 行,每行三个正整数 $u,v,w$,表示存在一条 $u$ 到 $v$ 距离为 $w$ 的单向路径。$(1 \leq u,v \leq n,1 \leq w \leq 10^9)$

然后一行一个正整数 $q$ ,表示 $ZC$ 搭建的道路数。 $(1 \leq q \leq 5 \times 10^4)$

接下来 $q$ 行,每行五个正整数,对应上文中 $ZC$ 搭建道路的方式。$(1 \leq u,L,R \leq n,1 \leq w \leq 10^9)$

$1$ $u$ $L$ $R$ $w$

$2$ $L$ $R$ $u$ $w$

Output

输出 $n$ 行,每行一个正整数,表示 $ZC$ 到学妹 $i$ 的距离。(包括 $ZC$ 自己)

如果 $ZC$ 无法到达,则输出 $-1$ 。

Samples

input
5 4 1 2 5 1 4 10 2 3 1 3 4 2 1 1 1 3 5 7
output
0 5 6 7 7

Author

ZHANG, Kaili