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