题目描述

For their physical fitness program, N (2 le N le 1,000,000) cows have decided to run a relay race using the T (2 le T le 100) cow trails throughout the pasture.

Each trail connects two different intersections (1 le I1i le 1,000; 1 le I2i le 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 le lengthi le 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

给出一张无向连通图，求S到E经过k条边的最短路。

输入输出格式

输入格式

• Line 1: Four space-separated integers: N, T, S, and E

• Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

输出格式

• Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

输入输出样例

输入样例 #1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例 #1

10