Minimum Transmission Time

Given a network of n servers and m bidirectional communication links, each with an associated transmission cost, your task is to determine the minimum time required to transmit a file from server A to server B.

Each communication link connects two servers and has a cost. The network can be modeled as an undirected weighted graph. The goal is to compute the shortest path from server A to server B using the links available. Formally, if we denote the transmission cost of a link as c, then you need to find the minimum sum of costs along any path from A to B.

If no path exists between A and B, output -1.

In mathematical notation, if d(u,v) represents the minimum transmission cost from server u to server v, then you are to determine:

$$ d(A,B)=\min_{\text{paths }P\;\text{from }A\text{ to }B}\sum_{(u,v)\in P} c(u,v) $$

where the sum is taken over all links in the path P.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains four integers: N M A B where:
• N is the number of servers.
• M is the number of communication links.
• A is the starting server.
• B is the destination server.
• Each of the next M lines contains three integers: U V C where there is a bidirectional link between servers U and V with a transmission cost of C.

outputFormat

Output a single integer to standard output (stdout): the minimum transmission time required from server A to server B. If no route exists, output -1.

## sample

5 6 1 5
1 2 10
1 3 20
2 3 5
2 4 1
3 4 3
4 5 2

13