Heat Wave

Problem Background

Special for beginners, ^_^

Problem Description

The simple folk of Texas are suffering a huge heat wave this summer!!! Their Texas Longhorn cattle taste good, but they are not very good at producing dairy products rich in cream. Farmer John, with the spirit of worrying about the world before the world worries and enjoying the world after the world enjoys, takes the lead in taking on the important task of transporting large amounts of nutritious, cool milk from Wisconsin to Texas, to ease the pain of the Texans enduring the heat.

FJ has studied the routes that can transport milk from Wisconsin to Texas. These routes pass through $T$ ($1 \le T \le 2,500$) towns including the start and the end, conveniently numbered $1$ to $T$. Every town other than the start and the end is connected to at least two other towns by two bidirectional roads. Each road has a passing cost (including fuel, tolls, etc.).

Given a map containing $C$ ($1 \le C \le 6,200$) roads directly connecting $2$ towns. Each road consists of its starting town $Rs$, ending town $Re$ ($1 \le Rs \le T$; $1 \le Re \le T$), and cost ($1 \le C_i \le 1,000$). Find the minimum total cost from the starting town $Ts$ ($1 \le Ts \le T$) to the ending town $Te$ ($1 \le Te \le T$).

Input Format

The first line: $4$ integers separated by spaces: $T, C, Ts, Te$.

Lines $2$ to $C+1$: the $(i+1)$-th line describes the $i$-th road. It contains $3$ integers separated by spaces: $Rs, Re$ and $C_i$.

Output Format

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

Sample Input

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

Sample Output

7

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.