Jam Factory

Gru is making jam in his underground laboratory to start a new legitimate career. Minions crush fruit in several giant vats. To make jam, the vats have to be joined by large pipes. His last batch failed, so Gru wants to combine two kinds of fruit this time.

You are given the cost of joining pairs of vats with pipes. Find the cheapest way to connect vat v1 and vat v2 to vat vd, the one that leads to the bottling machine. Fruit from v1 and fruit from v2 must both reach vd. The two routes may share part of the piping, and they do not have to. A shared pipe is paid for once. In some cases it is not possible to connect both vats to the vat leading to the bottling machine.

The figure shows two examples. Each one has 5 vats and 5 possible pipes, and vats 1 and 2 must be connected to vat 5, which leads to the bottling machine. On the left every pipe costs 1, so the minimum cost is 3, reached by building the pipes 1-4, 2-4, and 4-5 (the solid lines). On the right the pipe between vats 1 and 4 costs 4 instead. The minimum cost is then 4, reached by building the pipes 1-3, 3-5, 2-4, and 4-5 (the solid lines).

The input can be quite large. A single test case may have several hundred vats and several thousand possible pipes, so checking every possible set of connections does not finish within the time limit.

The input has several test cases. The first line of each test case has five integers: the number of vats v, the number of possible pipes p, the numbers of the two vats to be connected (v1 and v2), and the number of the vat connected to the bottling machine (vd).

Each of the next p lines has three integers vx, vy, and c, meaning that a pipe between vat vx and vat vy costs c. A pipe carries fruit in both directions. Vats are numbered 1 to v, and every cost is a non-negative integer. The same pair of vats may appear more than once, and a line where vx equals vy is possible.

A line containing only 0 follows the last test case.

For each test case, print the lowest cost on one line in this format:

Cost of connecting v1 and v2 to vd is c

Here v1, v2, and vd are the numbers given in the input and c is the lowest cost. If either vat cannot be connected to vd, print this line instead:

Cannot connect v1 and v2 to vd