Broken Gearbox

The Mechanical Turk was an 18th-century fake robot that created the illusion of artificial intelligence by playing chess. It inspired us to build our own fake robot, one that creates the illusion of real intelligence by solving programming contest problems.

To make the machine look more convincing, we mounted gears on axles inside an uncovered panel. The gears are purely decorative, so we placed them to form an impressive meshing pattern without any regard for gear ratios or turning direction. It is entirely possible that none of the gears can actually turn.

It is guaranteed that every axle was connected to every other axle by meshing, either directly or indirectly. Two axles $a$ and $b$ have directly meshing gears when their distance equals the sum of the radii of their gears, that is, $d_{ab} = r_{g_a} + r_{g_b}$.

Sadly, the gears fell off the machine. We believe we collected all of them, but we no longer know which gear belongs on which axle. Find a way to put the gears back on the axles so that they mesh the way they did originally.

The input consists of:

• One line with an integer $n$ ($2 \le n \le 10^5$), the number of gears and axles.
• One line with $n$ integers $r_1, \ldots, r_n$ ($1 \le r_i \le 10^8$), the radius of each gear.
• One line with an integer $m$ ($n - 1 \le m \le 10^5$), the number of pairs of axles to mesh.
• $m$ lines, each with three integers $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le n$, $1 \le d_i \le 10^8$): the indices of two axles that were directly meshed, and the distance between them.

If the machine can be fixed with the given gears, output $n$ integers $g_1, \ldots, g_n$ on one line, separated by spaces, where $g_i$ is the 1-based index of the gear to put on the $i$-th axle. The sequence $g_1, \ldots, g_n$ must be a permutation of $1$ to $n$. If several valid placements exist, output the lexicographically smallest sequence $g_1, \ldots, g_n$: at the first position where two sequences differ, the one with the smaller gear index comes first. Otherwise, output impossible.