2022寒假翻译10

公共交通系统

5000 ms 262144 k

描述：

你生活在一个交通发达的国家。这个国家有n个从1到n编号的城市和m条从1到m编号的公共交通路线。编号为i的路线是从城市ui到城市vi的有向路线，成本为ai，优惠因子为bi。为了方便人们出行，政府制定了一系列优惠措施。从s市出发，经过e1、e2、…、ek线路，以t市为终点，每条线路的成本计算如下:

路线e1，费用为ae1。

路线ei(> 1),如果aei > aei?1,成本aei?bei,否则成本aei。

旅行的总成本是这些路线成本的总和。

你现在住在城市1。对于每个k∈[1,n]，你想要找出从城市1到城市k的最小旅行成本。

输入：

输入的第一行包含一个整数T(1≤T≤10^4)，表示测试用例的数量。

每个测试用例的第一行包含两个整数n,m(2≤n≤10^5,1≤m≤2×10^5)，表示城市和路径的数量。

对于下面的m行，第i行包含4个整数ui,vi,ai,bi(1≤ui,vi≤n, ui≠vi, 1≤bi≤ai≤10^9)，表示编号为i的路由。

它保证所有测试用例中的n的和不超过6×10^5, m的和不超过1.2×10^6。

输出：

对于每个测试用例，输出一行包含n个用空格隔开的整数，第k个整数是从城市1到城市k的最小花费，或者如果你不能到达城市k，则输出?1。

不要在每一行的末尾打印任何额外的空格。

样例输入：

2

4个4

1 2 3 2

2 3 4 1

1 3 7 5

4 3 2 1

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

样例输出：

0 3 6 -1

0 8 6 10