题目描述
给出一个无向图,包含n个顶点(n<=2000),和m条边(m<=100000),图中顶点编号为1到n,边权值均为不超过1000的正整数,求编号为1的点到其他点的最短路长度
输入描述
输入的第一行为两个正整数,代表题目描述中的n,m
接下来m行,每行3个正整数x,y,z,表示图中存在一条x和y之间,权值为z的边
输出描述
输出一行,每行n个正整数,每个正整数后跟一个空格,第i个正整数代表顶点1到顶点i+1的最短路长度,如果不存在最短路则输出-1
样例输入
3 3
1 2 1
2 3 1
1 3 4
样例输出
1 2
提示