Minimum Assembly Time

You are given a directed graph representing the assembly procedure of a toy car. Each node represents a part and each directed edge from node u to node v has an associated time cost w for assembling part v after part u is completed. The toy car is assembled by starting at part 1 and finishing at part n. Your task is to determine the minimum total assembly time required to go from part 1 to part n.

If there is no valid assembly order (i.e. if the assembly cannot be completed or the dependency cycle prevents a valid ordering), output impossible.

The recurrence that is used for updating the minimum time is given by:

$$time[v] = \min(time[v],\; time[u] + w)$$

where the update is performed for every edge from u to v with weight w.

inputFormat

The input is read from stdin and begins with a single integer T representing the number of test cases. Each test case is described as follows:

• The first line contains two integers n and m, where n is the number of parts (numbered 1 to n) and m is the number of directed edges.
• This is followed by m lines, each containing three integers u, v, and w, representing a directed edge from part u to part v with an assembly time of w.

Note: All numbers are space-separated.

outputFormat

For each test case, output the minimum assembly time required to assemble the toy car. If it is impossible to assemble the toy car (i.e. part n cannot be reached), output impossible.

Print each result on a separate line to stdout.

## sample

5
2 1
1 2 3
3 2
1 2 2
2 3 1
4 3
1 2 2
2 3 3
3 4 1
3 3
1 2 2
2 3 1
3 1 4
5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 5 10

3
3
6
impossible
4

</p>