只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
405002 - 地图
有一张地图类似图
所示。现在要从A点出发，找到一条最短的路径到其他各点，试编程解决该问题。
Input
输入有若干行，第一行为一个整数n，表示共有n个地点。 随后n行，每行n个数，分别表示该地点与其他地点之间路线的长度，如果两点间没有路径则以-1表示。
Output
输出n行，每行一个整数，依次表示地点1到其他各点的最短路径。
Examples
Input
6 -1 6 3 -1 -1 -1 -1 -1 -1 5 -1 -1 -1 2 -1 3 4 -1 -1 -1 -1 -1 2 3 -1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1
Output
0 5 3 6 7 9
Hint
对于40％的数据，保证有n＜100； 对于60％的数据，保证有n＜256； 对于全部的数据，保证有n≤1 501。