Heat Wave

Texas is suffering a heat wave this summer. Farmer John is in charge of delivering plenty of ice-cold milk from Wisconsin to Texas so the Texans can beat the heat.

The routes that can carry the milk pass through a total of $T$ towns, numbered $1$ through $T$ (including the starting and ending towns). Each road connects two towns bidirectionally and has a traversal cost (gasoline, tolls, and so on).

Below is an example map of seven towns. Town $5$ is the source of the milk and town $4$ is its destination; the bracketed integers are the traversal costs.

                              [1]----1---[3]-
                             /               \
                      [3]---6---[4]---3--[3]--4
                     /               /       /|
                    5         --[3]--  --[2]- |
                     \       /        /       |
                      [5]---7---[2]--2---[3]---
                            |       /
                           [1]------

For example, traversing $5 \to 6 \to 3 \to 4$ costs $3 + 4 + 3 = 10$.

Given all $C$ roads (each described by its two endpoints $R1_i$, $R2_i$ and cost $C_i$), find the smallest total cost to travel from the starting town $T_s$ to the destination town $T_e$.

Constraints: $1 \le T \le 2500$, $1 \le C \le 6200$, $1 \le R1_i, R2_i \le T$, $1 \le C_i \le 1000$, $1 \le T_s, T_e \le T$.

• Line 1: Four space-separated integers $T$, $C$, $T_s$, and $T_e$.
• Lines $2$ through $C+1$: Line $i+1$ describes road $i$ with three space-separated integers $R1_i$, $R2_i$, and $C_i$.

• Line 1: A single integer, the total cost of the shortest route from $T_s$ to $T_e$. At least one route is guaranteed to exist.

In the sample input, the shortest route is $5 \to 6 \to 1 \to 4$ with cost $3 + 1 + 3 = 7$.