Description

The simple folks of Texas are suffering from a massive heatwave this summer!!! While their Texas Longhorns make for great beef, they aren't very skilled at producing creamy dairy products.
Farmer John, embodying the spirit of "worrying before the world worries and enjoying after the world enjoys," has taken the lead in shouldering the critical task of delivering large quantities of nutritious, ice-cold milk to Texas to alleviate the suffering caused by the scorching heat.
FJ has already researched the routes to transport milk from Wisconsin to Texas. These routes pass through a total of T (1 ≤ T ≤ 2,500) towns, conveniently labeled from 1 to T, including the starting and ending points. Every town, except the start and end points, is connected to at least two other towns via two bidirectional roads. Each road has an associated travel cost (including fuel, tolls, etc.).
Given a map containing C (1 ≤ C ≤ 6,200) direct roads connecting pairs of towns, each road is defined by its starting point Rs, ending point Re (1 ≤ Rs ≤ T; 1 ≤ Re ≤ T), and cost (1 ≤ Ci ≤ 1,000).
The task is to find the minimum total cost to travel from the starting town Ts (1 ≤ Ts ≤ T) to the destination town Te (1 ≤ Te ≤ T).

Input Format

• Line 1: Four space-separated integers: T, C, Ts, Te.
• Lines 2 to C+1: Each line describes a road with three space-separated integers: Rs, Re, and Ci.

Output Format

A single integer representing the minimum total cost from Ts to Te. The data guarantees that at least one valid path exists.

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

7

Hint

【Sample Explanation】 5->6->1->4 (3 + 1 + 3)