Exact-Trail Relay

Time limit2sMemory limit128 MB

Summary
Compute the minimum total length of a walk between two intersections that uses exactly N trails, where N can be as large as one million.
Level

Hard8 of 10

Topics
Shortest path, Matrix, Graph, Math
Solved
No attempts yet

Problem

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.

Input

  • 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.

Output

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

Examples2

  1. Example 1

    Input
    2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
    Expected output
    10

  2. Example 2

    Input
    12 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
    Expected output
    30