Problem Description
Ranald the cat wants to get some supplies from some faraway land and return back home. Since the 'faraway land' is so far away, there might or might not be direct transportation services/routes to that location from Ranald's house.
Ranald has investigated the bus routes from his house to the faraway land and has counted a total of N bus stops/interchanges labelled from 0 to N-1 and E bus routes. Each bus route costs a certain amount of money (C) and ferries people from bus stop A to bus stop B
A person (or cat) can get from one bus stop to another via buses (you don't say) but since some routes aren't bi-directional, the cost of travelling from bus stop 1 to bus stop 2 could be different from travelling from bus stop 2 to bus stop 1.
Ranald wants to know how much money would he need to spend on transportation if he decides to get the supplies and return back home. (If it costs too much, he can order it from Ebay ^^)
No 2 routes will have the same A and B.
Input
The first line of input consists of 4 integers: N, E, H and T. H represents which bus stop Ranald the cat will be starting in and T represents which bus stop the supplies Ranald wants would be located at.
Subsequently, E lines follow with 3 integers each: A, B and C. Each line describes a bus route, meaning there is a bus service that services from bus stop A to bus stop B and requires $C.
Output
Output a single integer, the amount of money Ranald would spend on transportation if he decides to go get the supplies and returns home.
If it is impossible (no route) to get the supplies and return home, output -1 instead.
Limits
0 ≤ A, B, H, T < N
0 ≤ C ≤ 10000
Subtask 1 (20%): 0 < N ≤ 5
Subtask 2 (30%): 0 < N ≤ 100
Subtask 3 (50%): 0 < N ≤ 1000
Sample Input 1
4 8 0 3
0 1 1
1 0 4
1 3 5
1 2 3
2 0 3
2 3 1
2 1 8
3 2 6
Sample Output 1
14
Explanation for Sample Output 1
It takes $5 to get from bus stop 0 to bus stop 3. It takes $9 to get from bus stop 3 to bus stop 0.
Sample Input 2
4 8 1 3
0 1 1
1 0 4
1 3 5
1 2 3
2 0 3
2 3 1
2 1 8
3 2 6
Sample Output 2
14
Explanation for Sample Output 2
It takes $4 to get from bus stop 1 to bus stop 3. It takes $10 to get from bus stop 3 to bus stop 1.
Sample Input 3
5 5 1 3
0 1 5
1 2 3
2 3 2
3 4 1
4 2 4
Sample Output 3
-1
Explanation for Sample Output 3
Although it is possible to get from bus stop 1 to bus stop 3 using $5, there is no way to get from bus stop 3 to bus stop 1.