卡赞群岛

Grade Open Time Friday, 19 September 2014, 10:05 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:05 am
Allow late Yes Close Time Friday, 26 September 2014, 10:05 am
Input file kezan.in Output file kezan.out

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

输入格式
第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