世界的尽头

英文题名：E. The end of this world,
来源：Codeforces 2239E
比赛：Codeforces Round 1105 (Div. 1)
时间限制：5 seconds
空间限制：1024 megabytes

题目描述

给定无向图。点有价值，边有容量 $w$ 和下界 $low$。出发前选 $h_{start}$，只有当当前状态 $h\le w$ 时才能过边，过边后状态变为 $\max(h,low)$。必须至少走一条边，得分为终点价值加 $h_{start}$。求每个起点最大得分。

输入格式

第一行输入 $t$。每组输入 $n,m$、点权和 $m$ 条边。

输出格式

每组输出 $n$ 个数，不可走边的起点输出 $-1$。

样例

9
3 2
10 20 5
1 2 5 2
2 3 4 3
2 1
100 10
1 2 10 5
2 0
50 50
1 0
114514
4 1
1 2 3 4
3 4 2 1
3 2
1 4 1
1 3 4 1
1 2 2 1
3 2
10 3 2
2 3 4 4
2 1 3 2
3 2
5 2 2
3 2 4 4
1 3 5 5
5 9
857147200 381798978 633421584 956726892 315899900
2 1 883474754 795831571
2 4 657281748 375466725
1 3 666641114 444218918
2 3 901861650 790895313
3 2 613790652 96876004
2 5 852725279 216601090
3 4 500240642 193633892
2 5 210434355 130646156
3 2 457018372 279005896

25 25 24
110 110
-1 -1
-1
-1 -1 6 6
6 6 6
13 13 7
10 9 10
1740621954 1740621954 1740621954 1614008640 1709872479