题目描述
给出一个有向图，输出节点1到所有节点，及所有节点到节点1，所有的最短距离之和。
输入
第一行一个整数t（1 ≤ t ≤ 10），表示数据组数。
对于每组数据：
第一行两个整数n和m（1 ≤ n,m ≤ 1000000），表示节点的数量和边的数量。
接下来m行，每行3个整数，分别表示每条边的起点、终点、长度。（长度不超过1000）
输出
n行，每行一个整数，表示题目所求的距离之和。
样例输入
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50样例输出
46
210