Absurdistan 的居民直到去年才学会如何修建道路。在这一发现之后，每个城市都决定修建一条连接本市与另一个城市的道路。每条新建的道路都可以双向通行。

Absurdistan 充满了令人惊讶的巧合。所有 $N$ 个城市花费了整整一年时间来修建各自的道路。更令人惊讶的是，最终可以通过这些新建的道路从任意一个城市到达其他所有城市。

你买了一本旅游指南，但里面没有包含新道路的地图。它只包含了一张巨大的表格，列出了使用这些新建道路后，所有城市对之间的最短距离。你想要知道哪些城市对之间有道路以及它们的长度，因为你想根据这张最短距离表重建这 $N$ 条新建道路的地图。

任务

给定一张 Absurdistan 中使用去年修建的 $N$ 条道路后所有城市对之间的最短距离表。你需要根据这张表重建 Absurdistan 的道路网络。可能存在多个拥有 $N$ 条道路且具有相同最短距离表的道路网络，但你只需要给出其中任意一个即可。

输入格式

对于每个测试用例：

• 一行包含一个整数 $N$ ($2 \le N \le 2000$) —— 城市和道路的数量。
• $N$ 行，每行包含 $N$ 个数字。第 $i$ 行的第 $j$ 个数字是城市 $i$ 到城市 $j$ 的最短距离。所有不同城市之间的距离均为正数且不超过 $1\,000\,000$。城市 $i$ 到 $i$ 的距离始终为 $0$，且城市 $i$ 到 $j$ 的距离与城市 $j$ 到 $i$ 的距离相同。

输出格式

对于每个测试用例：

• 输出 $N$ 行，每行包含三个整数 $a\ b\ c$，表示城市 $1 \le a \le N$ 和 $1 \le b \le N$ 之间存在一条长度为 $1 \le c \le 1\,000\,000$ 的道路，其中 $a \neq b$。如果存在多种解，你可以输出其中任意一个，且道路可以按任意顺序输出。保证至少存在一个解。

在每两个测试用例之间输出一个空行。

样例

输入 1

4
0 1 2 1
1 0 2 1
2 2 0 1
1 1 1 0
4
0 1 1 1
1 0 2 2
1 2 0 2
1 2 2 0
3
0 4 1
4 0 3
1 3 0

输出 1

2 1 1
4 1 1
4 2 1
4 3 1

2 1 1
3 1 1
4 1 1
2 1 1

3 1 1
2 1 4
3 2 3