A344. 想越狱的小衫
编程题
普及/提高-
知识点
题目描述
这次小杉来到了经典美剧《越狱》的场景里……他被抓起来了（-.-干嘛幻想这么郁闷的场景……）。
小杉身为新一代的Scofield，在挖了半个月之后终于挖通牢房里的地道。
在地道里，无数的管道路线困惑了他。
小杉看了看自己的纹身，明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。
小房间编号为不超过$N$的正整数。
对于某个管道，小杉只能在人品不超过一定程度时通过。
小杉一开始在房间$1$，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。
注意，小杉的人品在出发以后是不会改变的。
小杉身为新一代的Scofield，在挖了半个月之后终于挖通牢房里的地道。
在地道里，无数的管道路线困惑了他。
小杉看了看自己的纹身，明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。
小房间编号为不超过$N$的正整数。
对于某个管道，小杉只能在人品不超过一定程度时通过。
小杉一开始在房间$1$，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。
注意，小杉的人品在出发以后是不会改变的。
输入格式
每组测试数据的第一行有一个正整数$N(1\le N\le 2000)$。
接下来若干行描述管道，每行三个正整数$A,B,R(1\le A,B \le N)$，表示$A$房间有一条到达$B$房间的管道，且小杉的人品不超过$R$时可以通过（注意从$B$房间不可由此管道到达$A$房间，即管道是单向的)
整个输入数据以一行0 0 0结束
特别地，对于$30\%$的数据，有$N\le 100$，对于$100\%$的数据，有$N\le 2000$.
接下来若干行描述管道，每行三个正整数$A,B,R(1\le A,B \le N)$，表示$A$房间有一条到达$B$房间的管道，且小杉的人品不超过$R$时可以通过（注意从$B$房间不可由此管道到达$A$房间，即管道是单向的)
整个输入数据以一行0 0 0结束
特别地，对于$30\%$的数据，有$N\le 100$，对于$100\%$的数据，有$N\le 2000$.
输出格式
对每组测试数据输出$N-1$行，分别表示对于$2$到$N$号的小房间，小杉最多能够以人品多少的状态到达。
输入输出样例
输入 #1
4 1 2 30 1 3 20 2 3 25 3 4 30 2 4 20 0 0 0
输出 #1
30 25 25