【问题描述】

在世界上的某个山区，有一个由n个村庄组成的部落。这些村庄由一系列道路所连接，道路允许双向行驶。由于地形险恶，修建这些道路的费用很高，因此需要修建最少的道路，并使每个村庄都可以通过一系列道路互相到达。

这些村庄之间的贸易非常重要，因为并非每个村庄都能获得相同的自然资源供应。然而，许多村庄生产相同的资源，因此，了解村庄与其他村庄的相对距离是很有用的，这样他们就可以选择贸易伙伴，以最大限度地降低总体贸易成本。注意，两个村庄a和b之间的距离是连接a和b的最短路径上的各条道路的长度之和。

一个计算每对村庄之间距离的项目正在进行中。这些信息已包含在一张表格中，同时还有一张显示村庄布局和村庄之间道路的地图，你的任务是把表格和地图分发到所有的村庄，以促进村庄经济的发展。

不幸的是，就在你这项任务后不久，一阵风把你手中的地图吹到了乡下。尽管你尽了最大的努力寻找它，但你还是无法找到它。你知道你可以访问所有的村庄来重建地图，然后开始分发地图和表格，但这将花费原来任务的两倍时间，村庄会对你非常不满。你可能会想，也许只根据表格才能重建地图？

【输入】

第一行输入将包含整数n（2≤n≤2500），即该地区的村庄数量。接下来的n行每亩行包含n个整数。第i行第j列是从村庄i到村庄j的距离。所有距离都大于零（除非i=j），小于10000000，并且保证从村庄i至村庄j的距离与从村庄j至村庄i的距离相同。

【输出】

输出n-1行，每行上有两个整数u和v，表明该区域有一条连接村庄u和v的道路。能让所有村庄都能连通且路径最短。

【样本输入1】

4

0 1 1 2

1 0 2 3

1 2 0 3

2 3 3 0

【样本输出1】

1 2

1 3

1 4

【样本输入2】

7

0 2 9 1 4 3 3

2 0 11 1 6 3 3

9 11 0 10 5 12 12

1 1 10 0 5 2 2

4 6 5 5 0 7 7

3 3 12 2 7 0 4

3 3 12 2 7 4 0

【样本输出2】

1 4

1 5

2 4

3 5

4 6

4 7