地图
描述
有一张地图类似图
所示。现在要从A点出发，找到一条最短的路径到其他各点，试编程解决该问题。
输入
输入有若干行，第一行为一个整数n，表示共有n个地点。 随后n行，每行n个数，分别表示该地点与其他地点之间路线的长度，如果两点间没有路径则以-1表示。
输出
输出n行，每行一个整数，依次表示地点1到其他各点的最短路径。
样例
输入
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
输出
0 5 3 6 7 9
提示
对于40％的数据，保证有n＜100； 对于60％的数据，保证有n＜256； 对于全部的数据，保证有n≤1 501。
