섬

한 섬이 변이 $2n$개인 볼록 다각형 모양이다. 이 섬은 $2n-2$개의 나라로 나뉘어 있는데, 각 나라는 다각형의 꼭짓점들을 세 꼭짓점으로 하는 삼각형 모양이다. 즉, 서로 교차하지 않는 대각선들로 다각형을 삼각형들로 나눈 것이다.

어떤 나라도 정확히 두 나라와만 국경을 맞대고 있지는 않다. 모든 나라는 한 나라 또는 세 나라와 국경을 맞댄다. 따라서 정확히 한 나라와만 국경을 맞대는 나라가 $n$개(이들을 해안 나라라 한다), 세 나라와 국경을 맞대는 나라가 $n-2$개(이들을 내륙 나라라 한다) 있다. 해안 나라에는 $1$번부터 $n$번까지, 내륙 나라에는 $n+1$번부터 $2n-2$번까지 번호가 매겨진다.

국경을 넘을 때에는 통행료를 낸다. 국경마다 통행료가 다를 수 있지만, 한 국경을 넘는 비용은 양방향 모두 같다. 각 통행료는 $1$ 이상 $100$ 이하의 정수이다.

두 해안 나라 $i$와 $j$의 모든 쌍에 대해, 넘는 국경의 수가 가장 적은 경로로 $i$에서 $j$까지 갈 때 내는 통행료의 합이 주어진다. (나라들의 국경 구조는 트리를 이루므로 이 경로는 유일하다.) 이 정보로부터 섬의 모든 국경과 그 통행료를 복원하라. 즉, 각 나라에 대해 이웃 나라들과 맞댄 국경 각각의 통행료를 구하라.

첫 줄에 해안 나라의 수 $n$ ($4 \le n \le 100$)이 주어진다.

다음 $n$개의 줄에는 각각 $n$개의 음이 아닌 정수가 공백 하나로 구분되어 주어진다. $i$번째 줄의 $j$번째 정수 $d_{i,j}$는 해안 나라 $i$에서 해안 나라 $j$까지, 넘는 국경의 수가 가장 적은 경로로 갈 때 내는 통행료의 합이다. 입력은 $d_{i,j}=d_{j,i}$와 $d_{i,i}=0$을 만족하며, 모든 국경의 통행료가 $[1,100]$ 범위의 정수인 어떤 섬과 반드시 일치한다.

국경들을 설명하는 $2n-2$개의 줄을 출력한다.

처음 $n$개의 줄에는 해안 나라를 하나씩 설명한다. $i$번째 줄($1 \le i \le n$)에는 두 정수를 출력하는데, 해안 나라 $i$와 국경을 맞댄 나라의 번호와 그 국경의 통행료이다.

다음 $n-2$개의 줄에는 내륙 나라를 하나씩 설명한다. 내륙 나라 $c$($n+1 \le c \le 2n-2$)의 줄에는 여섯 개의 정수를 출력하는데, 세 이웃 나라를 이웃 번호가 작은 순서로 나열하되 각 이웃에 대해 그 번호와 맞댄 국경의 통행료를 함께 적는다.

답이 유일해지도록 내륙 나라의 번호를 다음과 같이 결정한다. 국경 트리를 해안 나라 $1$번과 국경을 맞댄 내륙 나라에서 시작해 깊이 우선으로 탐색하며 $n+1, n+2, \ldots, 2n-2$를 붙인다. 탐색이 어떤 내륙 나라에 처음 도달하는 순간 아직 쓰지 않은 가장 작은 번호를 그 나라에 부여한다. 각 내륙 나라에서는, 그 국경을 통해 (지금 있는 나라로 되돌아가지 않고) 도달할 수 있는 해안 나라 번호의 최솟값이 작은 순서대로 아직 번호가 매겨지지 않은 이웃 내륙 나라로 이동한다.

아래 그림은 이러한 섬의 한 예이다. 해안을 따라 있는 해안 나라들, 안쪽의 내륙 나라들, 그리고 그 사이의 국경들(과 통행료)을 보여준다.