Shortest Path in a Warehouse

You are given a warehouse represented as an undirected weighted graph with N locations and M bidirectional paths. Each path has an associated travel time. Your task is to find the shortest travel time from a starting location S to a target location T. If there is no path connecting S and T, output -1.

The travel time along a specific path is computed as:

[ \text{time} = \sum_{i=1}^{k} w_i ]

where \(w_i\) represents the weight of the i-th edge on the path.

Note: If the starting location is the same as the target location, the travel time is 0.

inputFormat

The first line contains four integers: N, M, S, and T, where N is the number of locations, M is the number of paths, S is the starting location, and T is the target location. Each of the next M lines contains three integers u, v, and w, representing a bidirectional path between locations u and v with travel time w.

outputFormat

Output a single integer representing the shortest travel time from location S to T. If no such path exists, output -1.## sample

5 6 1 5
1 2 4
1 3 2
2 3 5
2 4 10
3 4 3
4 5 7

12