Runaway Time Machines

Tim the time-traveling salesman owns several time machines that carry him to different points in space-time. The machines navigate a network of wormholes; each wormhole connects two space-time points and takes a fixed amount of time to cross. Tim's machines are fully automated and always follow a shortest path to their destination.

A recent, violent wormhole storm sent some of Tim's machines haywire. Each affected machine loaded the single destination stored in its memory bank and took off. When a machine finished its trip it broadcast a diagnostics signal reporting its starting point and the total time the trip took. Tim no longer remembers which destination each machine was programmed for, but he does know that no two machines were programmed for the same destination.

For each machine you are given its starting point and its total travel time; the machine's destination is a point whose shortest-path distance from the start equals that travel time. Decide whether the destinations of all machines can be uniquely determined.

The first line contains the number of data sets $K$. Then the $K$ data sets follow, each in the format below.

The first line of a data set contains three integers $M$, $N$, and $W$ ($1 \le M \le 20$, $2 \le N \le 100$, $N - 1 \le W \le 500$), where $M$ is the number of missing machines, $N$ is the number of space-time points, and $W$ is the number of wormholes. Machines are numbered $1$ to $M$ and points are numbered $1$ to $N$.

Each of the next $W$ lines contains three integers $a_i$, $b_i$, and $c_i$: wormhole $i$ connects points $a_i$ and $b_i$ and takes $c_i$ seconds to cross in either direction. No wormhole takes more than 1,000 seconds.

Each of the final $M$ lines contains two integers $s_i$ and $t_i$: the starting point and the total travel time in seconds of machine $i$. Every machine is guaranteed to have followed a valid shortest path to some destination, and no two machines share a destination.

For each data set, first output a line containing "Data Set x:", where $x$ is the number of the data set (starting from $1$).

If the destination of every machine is uniquely determined, output the destinations on a single line, from machine $1$ to machine $M$, separated by single spaces, with no leading or trailing whitespace. If the destination of one or more machines cannot be uniquely determined, output "impossible" instead.

Separate consecutive data sets with a blank line.