OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1223--最短路

1223: 最短路

时间限制: 1 Sec  内存限制: 128 MB
提交: 61  解决: 35
[提交] [状态] [讨论版] [命题人:]

题目描述

给出一个有向图，设起点为1，设Ai为起点到点i的最短路径距离，你请按1~n的顺序输出Ai。  

输入

第一行两个正整数n，m用空格隔开(n≤100，m≤1000)代表n个顶点，m条边。 
接下来m行每行三个整数u，v，w代表有一条权值为w的边从u到v，(1≤u,v≤n，1≤w≤100000)可能含有重边。 
样例解释如上。 

输出

一行n个数，含义如题目描述。 

样例输入 Copy 

6 10
1 2 3
3 4 2   
2 4 7
1 3 4
1 4 3
1 5 10
2 5 4
5 6 5
5 3 2
2 6 1

样例输出 Copy 

0 3 4 3 7 4

来源/分类

图论 
[提交] [状态]