고장 난 기어박스

기계 투르크는 18세기에 만들어진 가짜 로봇으로, 체스를 두어 인공지능이 있는 것처럼 보이게 했다. 우리는 여기서 영감을 받아 프로그래밍 대회 문제를 푸는 것처럼 보이는 가짜 로봇을 만들었다.

기계가 더 그럴듯해 보이도록 덮개가 없는 패널 안에 축을 세우고 톱니바퀴를 끼웠다. 톱니바퀴는 장식일 뿐이라 서로 맞물린 모양이 멋져 보이도록만 배치했고, 기어비나 회전 방향은 전혀 고려하지 않았다. 그래서 실제로는 어떤 톱니바퀴도 돌지 않을 수 있다.

모든 축은 직접 또는 다른 축을 거쳐 간접적으로 서로 맞물려 있었음이 보장된다. 두 축 $a$, $b$ 사이의 거리가 두 축에 끼운 톱니바퀴의 반지름 합과 같을 때, 즉 $d_{ab} = r_{g_a} + r_{g_b}$일 때 두 축의 톱니바퀴가 직접 맞물린다고 한다.

그런데 톱니바퀴가 모두 기계에서 떨어져 버렸다. 전부 다시 주웠다고 생각하지만, 어떤 톱니바퀴를 어느 축에 끼워야 하는지는 알 수 없다. 원래처럼 맞물리도록 톱니바퀴를 축에 끼우는 방법을 찾아라.

첫째 줄에 톱니바퀴와 축의 개수 $n$ ($2 \le n \le 10^5$)이 주어진다.

둘째 줄에 각 톱니바퀴의 반지름 $r_1, \ldots, r_n$ ($1 \le r_i \le 10^8$)이 주어진다.

셋째 줄에 맞물려야 하는 축 쌍의 개수 $m$ ($n - 1 \le m \le 10^5$)이 주어진다.

다음 $m$개의 줄에 세 정수 $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le n$, $1 \le d_i \le 10^8$)가 주어진다. 원래 직접 맞물려 있던 두 축의 번호와 두 축 사이의 거리다.

주어진 톱니바퀴로 기계를 고칠 수 있으면 $n$개의 정수 $g_1, \ldots, g_n$을 한 줄에 공백으로 구분해 출력한다. $g_i$는 $i$번 축에 끼울 톱니바퀴의 번호(1부터 시작)이며, $g_1, \ldots, g_n$은 $1$부터 $n$까지의 순열이어야 한다. 조건을 만족하는 배치가 여러 가지라면 수열 $g_1, \ldots, g_n$이 사전순으로 가장 앞서는 것을 출력한다. 즉, 처음으로 값이 달라지는 위치에서 더 작은 번호를 가진 수열이 앞선다. 고칠 수 없으면 impossible을 출력한다.