OI题库

问题描述
当联盟与部落的注意力还停留在诺森德之时，一股古老的邪恶力量正在土元素界——地深之源中沉睡。藏身在与世隔绝的圣殿里，堕落的守护巨龙——死亡之翼静静等着，等待从最后一次与艾泽拉斯交战时所受的伤势中复原；他以对地表上弱势生物的仇恨滋养自己；静候能用复活之火重新吞噬世界的时机来临。终于，“毁灭者”死亡之翼回到了艾泽拉斯，他从地深之源破巢而出的那一刻，整个世界被割裂，在大陆上留下了一道无法抹灭的伤痕。
 
原本安静的卡赞群岛，如今也被地震和洪水撕裂，地精们为了自己的生存，不得不结成商业联盟——只有极少数地精还保持中立。地精的商业联盟为了各自的利益，互相设置了很多贸易壁垒，群岛之间的昂贵得匪夷所思的船票就是一个典型的例子。卡赞群岛由很多岛屿组成，岛屿之间有很多航线。依靠垄断海上贸易，各个商业联盟都控制了一些岛屿。如果两个岛屿之间有不止一条路径可以到达，那么这两个岛屿一定是被一个商业联盟控制的，否则这两个岛屿属于两个不同的商业联盟的控制之下。
 
菲利克斯作为一个中立者，靠在各个商业联盟之间投机获取利润，因此要经常在岛屿之间旅行。菲利克斯已经骗取了所有的商业联盟的信任，所以在一个商业联盟内部的岛屿间旅行全部是免费的，只有乘坐跨两个商业联盟控制的岛屿的航线才用付出费用。菲利克斯从任何一个岛屿开始，前往别的岛屿都会采用费用最小的路线。尽管如此，为了估计支出，菲利克斯想知道从每个岛屿出发，到其他岛屿的最大费用。

输入格式
第1行，两个整数N,M，表示有N个岛屿，M条航线。
接下来M行，每行三个整数a,b,c，表示岛屿a,b(1<=a,b<=N)之间有一条费用为c的航线。

输出格式
共N行，第i行为从岛屿i出发到达别的岛屿费用的最大值。
 
样例输入
6 6
1 4 2
1 2 6
2 5 3
2 3 7
6 3 4
3 1 8

样例输出
4
4
4
6
7
7

样例说明
有四个商业联盟，控制的岛屿分别为{1,2,3},{4},{5},{6}。从岛屿1出发到达岛屿6，乘坐(1,3)(3,6)两个航线费用最大，(1,3)为免费航线，(3,6)的费用为4，所以从1出发的最大费用为4。

数据规模
30%的数据满足1<=N<=1000，1<=M<=1000;
100%的数据满足1<=N<=20000,1<=M<=200000。

by   BYVoid