"Shortest" Pair of Paths

A chemical company has an unusual shortest path problem.

There are $N$ depots (vertices) where chemicals can be stored, and $M$ individual shipping methods (edges) connecting pairs of depots. Each individual shipping method has a cost. In the usual problem, the company would need only to route a single shipment from the first depot ($0$) to the last ($N - 1$); that is easy. The problem they have is harder: they have to ship two chemicals from the first depot ($0$) to the last ($N - 1$). The chemicals are dangerous and cannot safely be placed together. The regulations say the company cannot use the same shipping method for both chemicals. Further, the company cannot place the two chemicals in the same depot (for any length of time) without special storage handling, which is available only at the first and last depots.

To begin, they need to know whether it is possible to ship both chemicals under these constraints. Next, they need to find the least cost of shipping both chemicals from the first depot to the last depot. In brief, they need two completely separate paths (from the first depot to the last) where the overall cost of both is minimal.

Your program must simply determine the minimum cost or, if it is not possible, conclusively state that the shipment cannot be made.

The input consists of multiple cases. The first line of each case contains $N$ and $M$, where $N$ is the number of depots and $M$ is the number of individual shipping methods. You may assume that $N$ is less than $64$ and that $M$ is less than $10000$. The next $M$ lines each contain three values, $i$, $j$, and $v$. Each line corresponds to a single, unique shipping method. The values $i$ and $j$ are the indices of two depots, and $v$ is the (non-negative integer) cost of getting from $i$ to $j$. Note that these shipping methods are directed: if something can be shipped from $i$ to $j$ with cost $10$, that says nothing about shipping from $j$ to $i$. Also, there may be more than one way to ship between any pair of depots, and that may be important here. A line containing two zeroes signals the end of the data and should not be processed.

For each case, print one line in the form Instance #k: C, where $k$ is the case number (starting from $1$) and $C$ is the minimum total cost of shipping both chemicals. If the shipment cannot be made, print Instance #k: Not possible instead. Note that there are two spaces after the colon.