Problem Description

The plain folks of Texas are suffering from a massive heat wave this summer!!!

Their Texas longhorn cattle taste good, but they aren`t very good at producing rich, creamy dairy products.

Farmer John has taken the lead in transporting large quantities of nutritious, ice-cold milk to Texas to relieve the Texans` suffering from the heat.

John has studied the routes that can be used to transport milk from Wisconsin to Texas.

These routes include a total of T towns, including start and end points, conveniently numbered 1 to T.

Every town except the start and end is connected by bidirectional roads to at least two other towns.

Each road has a travel cost (including fuel, tolls, etc.).

You are given a map containing C roads that directly connect 2 towns.

Each road is described by its starting point R_s, ending point R_e, and cost C_i.

Find the minimum total cost to travel from the starting town T_s to the destination town T_e.

Input Format
Line 1: Four space-separated integers: T, C, T_s, T_e
Lines 2 to C+1: Line i+1 describes the i-th road, containing three space-separated integers: R_s, R_e, C_i

Output Format
A single integer representing the minimum total cost from T_s to T_e.

The data guarantees at least one road exists.

Data Range
1 ≤ T ≤ 2500
1 ≤ C ≤ 6200
1 ≤ T_s, T_e, R_s, R_e ≤ T
1 ≤ C_i ≤ 1000

Input Sample:

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

Output Sample:

7