[Usaco2009 Jan]安全路经Travel

有 $N$ 个牛棚，编号为 $1$ 到 $N$，它们之间由 $M$ 条道路连接。每条道路连接两个不同的牛棚，均可双向通行，且通行时间为正整数。保证从牛棚 $1$ 可以到达其他所有牛棚。

从牛棚 $1$ 到每个牛棚的最短路径都是唯一的。对于每个牛棚 $i$（$2\le i\le N$），假设从牛棚 $1$ 到牛棚 $i$ 的最短路径上的最后一条道路无法通行，请求出不经过该道路时，从牛棚 $1$ 到牛棚 $i$ 所需的最少时间。如果不存在这样的路径，则输出 $-1$。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$，分别表示牛棚数量和道路数量。

接下来 $M$ 行，每行包含三个用空格分隔的整数 $a_i$、$b_i$ 和 $t_i$，表示牛棚 $a_i$ 与牛棚 $b_i$ 之间有一条双向道路，通行时间为 $t_i$。

输出格式

输出 $N-1$ 行。第 $i$ 行输出一个整数，表示从牛棚 $1$ 到牛棚 $i+1$，且不经过其唯一最短路径上最后一条道路时所需的最少时间。如果不存在这样的路径，则输出 $-1$。

样例输入

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

样例输出

3
3
6

数据范围

• $2\le N\le 10^5$；
• $N-1\le M\le 2\times 10^5$；
• $1\le a_i,b_i\le N$，且 $a_i\ne b_i$；
• $1\le t_i\le 10^4$；
• 保证从牛棚 $1$ 可以到达其他所有牛棚；
• 保证从牛棚 $1$ 到每个牛棚的最短路径唯一。

来源与许可

本题为 USACO 2009 January 试题「安全路径 Travel」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

3
3
6