Fetch Quest is a Co-op minigame appearing in Super Mario Party and you can view how the game is actually played here. In the game, there are four players in a maze, and the goal is to collaborate and fetch some crystal pieces to a given position. The maze can be modeled as a graph. There are $n$ vertices, each containing a crystal piece except for vertex 0 (the starting and ending point). There are $m$ edges connecting these vertices, each with a different length. The goal is to fetch all crystal pieces to vertex 0, which is also the starting point of all players. A player can carry at most one crystal piece at a time. Once picking up a crystal piece, one must carry it until they reach vertex 0, where they can put it down. In other words, once pick up a crystal piece, you cannot drop it off halfway. You must carry it to the destination (vertex 0).

The players can run through the edges. Traveling through each edge takes a different amount of time. Multiple players, or players and crystals won't block each other. Passing any vertex does not need extra time, nor does carrying a crystal piece. Given the graph, the time needed to travel through each edge, the position of all crystal pieces, and the number of players, please write a program to compute what is the minimum time needed to collect all the crystals.

The timeout of the game is 600 seconds (10 min). If the players do not finish within 600 seconds, the task will fail.

In the game, some paths are inaccessible without someone standing on a button. In this problem, we ignore this setting for simplicity.

Input Specification

The first line of the input contains two integers, $n$, which is the number of vertices, and $m$, which is the number of edges in the graph. The vertices will be labeled from 0 to $n-1$. All players start from vertex 0. There will be $n-1$ crystals at all vertices except for vertex 0. All the crystals also need to be carried back to vertex 0.

The next $m$ lines each contain two integers $x_i,y_i,t_i$, which means edge $i$ connects vertices $x_i$ and $y_i$ and requires $t_i$ seconds to travel through. All edges are bi-directional.

The graph is a simple graph (i.e., no parallel edges or self-loops).

Output Specification

If the tasks can be finished within 600 seconds (inclusive), the output only contains 1 integer, which is the shortest time needed to collect all crystals.

If the task cannot be finished within 600 seconds, output Impossible!.

Sample Input 1

6 6
0 1 1
1 2 1
0 2 1
0 3 1
3 4 1
3 5 1

Sample Output 1

4

Sample Input 2

7 8
0 1 7
1 2 1
0 2 12
0 3 8
3 4 2
3 5 9
4 5 5
0 6 9

Sample Output 2

32

Sample Input 3

7 8
0 1 140
1 2 20
0 2 240
0 3 160
3 4 40
3 5 180
4 5 100
0 6 180

Sample Output 3

Impossible!

Explanation for Sample Outputs

One of the best solutions for input 1 is to let player 1 grab crystal 1 (at vertex 1) and crystal 2 (at vertex 2). Player 2 should fetch crystal 3 (at vertex 3). Player 3 should fetch crystal 4 (at vertex 4). Player 4 should fetch crystal 5 (at vertex 5). After 4 units of time, they all finish.

One of the best solutions for input 2 is to let player 1 grab crystal 5 (30s). Player 2 should fetch crystal 4 (20s). Player 3 should fetch crystal 1 and crystal 6 (32s). Player 4 should fetch crystal 2 and crystal 3 (32s). After 32 seconds, they all finish.

For input 3, the best solution would be 640s, which is longer than 600s (note that the time needed in input 3 is always $20\times$ that of input 2).

Source of pictures and descriptions: https://www.mariowiki.com/Fetch_Quest. You can also find more details about the game from this site.

Scoring

For 20% of the tests:

$0<n\le 10$.

For 50% of the tests:

$0<n\le 20$.

For 100% of the tests:

$0<n\le 50$, $m<1000$.

There are 10 test cases, 15 points each.