最短路(roads)

题目描述

【传统的最短路题目中, 每条边的边权往往是固定的, 这令江老师十分不满。

于是江老师定义了一种全新的边权计算方式。

每条边有两个权值 $a,b$ 。对于一条路径, 假设其上的边依次为 $e_1,e_2,\dots,e_k$。

• 对于第一条边 $e_1$, 其边权为 $a_{e_1}$。
• 对于第 $i$ 条边 $e_i(i\ge 2)$, 若 $a_{e_{i-1}}

现在江老师请你求出从 $1$ 分别到每个点的最短路。

输入格式

第一行两个整数 $n,m$, 表示图中有 $n$ 个点, $m$ 条边。

接下来 $m$ 行每行有 $4$ 个整数 $u_i,v_i,a_i,b_i$, 表示存在一条 $u_i$ 指向 $v_i$ 权值为 $a_i,b_i$ 的有向边。

输出格式

输出一行共 $n$ 个整数, 其中第 $i$ 个表示从 $1$ 到 $i$ 的最短路长度, 若不存在 $1$ 到 $i$ 的路径则输出 $-1$。

样例

输入1

4 4
1 2 3 2
2 3 4 1
1 3 7 5
4 3 2 1

输出1

0 3 6 -1

输入2

4 8
4 2 3 3
1 3 6 3
4 2 10 5
1 2 8 2
3 2 4 3
4 2 7 7
3 4 4 2
1 2 8 1

输出2

0 8 6 10

样例4 对应Case 3-4

见样例文件夹

数据范围与提示

保证除 Case 1-2 不存在其他的数据满足 $m=n-1$, 你可以借此来判断数据类型。

对于全部数据, 保证 $1\le u,v\le n,u\ne v,1\le b_i\le a_i\le 10^9,2\le n\le 10^5,1\le m\le 2\cdot 10^5$。

(百度百科-外向树: 由有向边构成的，所有边的方向都是从父亲到儿子的有根树)