题目描述

精灵最近在农场上泛滥，它们经常会阻止牛们从农庄（牛棚 $1$）走到别的牛棚（牛 $i$ 的目的地是牛棚 $i$）。每一个精灵只认识牛 $i$ 并且知道牛 $i$ 一般走到牛棚的最短路经。所以它们在牛 $i$ 到牛棚 $i$ 之前的最后一条牛路上等牛 $i$。当然，牛不愿意遇到精灵，所以准备找一条稍微不同的路经从牛棚 $1$ 走到牛棚 $i$。所以，请你为每一头牛i找出避免精灵的最短路经的长度。

和以往一样，农场，上的 $m$ 条双向牛路编号为 $1$ 到 $m$ 并且能让所有牛到达它们的目的地，$n$ 个牛棚，牛路 $i$ 连接牛棚 $a_i$ 和 $b_i$ 并且需要时间 $t_i$ 通过。没有两条牛路连接同样的牛棚，所有牛路满足 $a_i\not =b_i$。在所有数据中，牛 $i$ 使用的牛棚 $1$ 到牛棚 $i$ 的最短路经是唯一的。

以下是一个牛棚，牛路和时间的例子：

当精灵进入农场后：

输入格式

第一行：两个空格分开的数，$n$ 和 $m$。

第 $2\sim m+1$ 行：三个空格分开的数 $a_i,b_i,t_i$。

输出格式

第 $1\sim n-1$ 行：第 $i$ 行包含一个数：从牛棚 $1$ 到牛棚 $i+1$ 并且避免从牛棚 $1$ 到牛棚 $i+1$ 最短路经上最后一条牛路的最少的时间。如果这样的路经不存在,输出 $-1$。

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

3
3
6

数据规模与约定

对于 $100\%$ 的数据，$2\leq m\leq 2\times 10^5$，$3\leq n\leq 1\times 10^5$，$1\leq a_i,b_i\leq n$，$1≤t_i≤1000$。

题目来源

Usaco 2009 Jan Gold