#P22402. Minimum Path
Minimum Path
题意
给定一张包含 个点 条边的无向图,无自环无重边,第 条边连接 两个节点,长度为 。
设一条路径经过的边集为 (多次经过仍会加入边集),则定义这条路径的长度为
$$\sum_{i\in E} w_i-\max_{i\in E} w_i +\min_{i\in E} w_i $$求编号为 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