想越狱的小杉

想越狱的小杉

测试数据来自 system/1391

背景

这次小杉来到了经典美剧《越狱》的场景里……
他被抓起来了(-.-干嘛幻想这么郁闷的场景……)。

小杉身为新一代的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

输出格式

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

样例1

样例输入1

4
1 2 30
1 3 20
2 3 25
3 4 30
2 4 20
0 0 0

样例输出1

30
25
25

限制

每个测试点1s

提示

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

来源

lolanv

信息

ID
1486
难度
(无)
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者