Problem
编写一个程序，在具有非负边长的无向加权图中找到从给定顶点到所有其他顶点的距离。该程序对于大型稀疏图应该很快。
输入
输入的第一行包含数字 NUM — Dijkstra 算法的不同运行次数（在不同的图形上）。接下来是 NUM 个块，每个块都具有以下结构。
块的第一行包含两个数字 N 和 M，中间用空格隔开—图的顶点数和边数。接下来是 M 行，每行包含三个由空格分隔的整数。其中前两个，范围从 0 到 N–1，表示相应边的端点，第三个 —范围从 0 到 20000，表示这条边的长度。此外，在块的最后一行，从 0 到 N–1 — 的单个数字。峰值，您需要搜索的距离。
一次测试中不同图的数量NUM不超过 5。顶点数不超过60000，边—— 200000.
印记
打印到标准输出（屏幕）NUM 行，每行包含 Ni 用空格分隔的数字 —从带权无向图的指定起始顶点到它的第 0、1、2 等的距离。顶点（最后一个数字后允许有一个额外的空格）。如果某个顶点无法从指定的初始顶点到达，则打印数字 2009000999 而不是距离（保证所有实际距离都更小）。
示例
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |