圣诞岛的旅行

问题描述：

Angel最近无聊，去了圣诞岛(CX *^_^*)，他喜欢无目的的乱逛，当然，他不会轻易地回头。Angel想去广场，那么，他什么时候才能到呢？你已经得到了CX的地图，地图上有N(N<=100)个交叉路口，交叉路口之间有马路相连接(不超过1000条马路)。因为CX的人遵循奇怪的规则，道路都是单向的，不同的道路之间有一定的距离，我们假设Angel所在的地点分别为点1，点2，…，点N-1，广场所在点为N。假设Angel走一单位距离需要一单位时间。问Angel分别从点1~点N-1出发，最早什么时候到达广场？
Input
第一行N和M，M是边的数量，以后M行，每行3个整数X，Y，Weight，代表一条从X城市到Y城市，长度为Weight的边。
Output
共N-1行数据，第K行是城市编号K->N:最少时间。要是可怜的Angel从城市K永远到不了广场，输出城市编号K->N：Never。
Sample Input
5 6
1 2 1
1 4 10
2 3 1
3 4 1
4 5 1
1 5 3
Sample Output
1->5:3
2->5:3
3->5:2
4->5:1

问题解答：

圣诞岛的旅行这个旅游问答期待您的解答，请登录账号或关注微信公众号回答这个问题。