Exact-Trail Relay

For a fitness program, N (2 <= N <= 1,000,000) cows will run a relay using the T (2 <= T <= 100) trails in a pasture.

Each trail connects two different intersections. Intersection labels are integers between 1 and 1,000, and every listed intersection is incident to at least two trails. For each trail, the cows know its length (1 <= length_i <= 1,000) and the two intersections I1_i and I2_i that it connects. No two intersections are directly connected by more than one trail.

The cows may stand at intersections, and more than one cow may stand at the same intersection. They need to pass the baton from cow to cow so that the route starts at intersection S, ends at intersection E, and uses exactly N trails.

Find the minimum possible total distance of such a route.

• Line 1: four space-separated integers N, T, S, and E.
• Lines 2 through T+1: line i+1 describes trail i with three space-separated integers length_i, I1_i, and I2_i.

Print one integer: the shortest distance from intersection S to intersection E using exactly N trails.