#P22402. Minimum Path

Minimum Path

题意

给定一张包含 nn 个点 mm 条边的无向图,无自环无重边,第 ii 条边连接 ui,viu_i,v_i 两个节点,长度为 wiw_i

设一条路径经过的边集为 EE(多次经过仍会加入边集),则定义这条路径的长度为

$$\sum_{i\in E} w_i-\max_{i\in E} w_i +\min_{i\in E} w_i $$

求编号为 1 的点到其他所有点的最短路径长度。

输入格式

第一行两个数 n,mn,m

接下来 mm 行,每行三个数 ui,vi,wiu_i,v_i,w_i 表示一条边。

输出格式

n1n-1 行,表示每个点的答案。

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