最短路

Tags:

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

Author