Minimum Travel Time

We are given several test cases, each representing an undirected weighted graph. In each test case, the first line contains four integers (n), (m), (s), and (t), where (n) is the number of nodes (locations), (m) is the number of edges (routes), (s) is the starting location, and (t) is the destination. Following this, there are (m) lines with three integers each, representing a route between two nodes and the travel time for that route. Your task is to compute the minimum travel time from (s) to (t) using Dijkstra's algorithm. If the destination is unreachable, output (-1).

Formally, given a graph (G=(V,E)) with (|V|=n) and (|E|=m) and two specified vertices (s) and (t), find the minimum distance from (s) to (t). If no path exists, print (-1).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (T), the number of test cases. For each test case:

• The first line contains four integers: \(n\) \(m\) \(s\) \(t\), where \(n\) is the number of locations, \(m\) is the number of routes, \(s\) is the starting location, and \(t\) is the destination.
• Then \(m\) lines follow, each with three integers: \(u\), \(v\), and \(w\), denoting a bidirectional route between locations \(u\) and \(v\) with travel time \(w\).

outputFormat

For each test case, output the minimum travel time from (s) to (t) on a separate line. If there is no path, output (-1). The output should be sent to standard output (stdout).## sample

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

10
15