小杉看了看自己的纹身，明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。 小房间编号为不超过N的正整数。 对于某个管道，小杉只能在人品不超过一定程度时通过。 小杉一开始在房间1，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。 注意，小杉的人品在出发以后是不会改变的。

每组测试数据的
第一行有一个正整数N(1< =N< =2000)。
接下来若干行描述管道，每行三个正整数A,B,R(1< =A,B< =N)，表示A房间有一条到达B房间的管道，且小杉的人品不超过R时可以通过（注意从B房间不可由此管道到达A房间，即管道是单向的)
整个输入数据以一行0&nbsp 0&nbsp 0结束

特别地，对于30%的数据，有N< =100

对每组测试数据输出N-1行，分别表示对于2到N号的小房间，小杉最多能够以人品多少的状态到达。

4
1 2 30
1 3 20
2 3 25
3 4 30
2 4 20
0 0 0
 \n
 · ·  \n
 · ·  \n
 · ·  \n
 · ·  \n
 · ·  \n
 · · \n

30
25
25
  \n
  \n
  \n

对于样例数据：
小杉最多能够在人品为30的情况下到达小房间2(1-> 2)
小杉最多能够在人品为25的情况下到达小房间3(1-> 2-> 3)
小杉最多能够在人品为25的情况下到达小房间4(1-> 2-> 3-> 4)