Shortest Path using Floyd-Warshall Algorithm

Given an undirected weighted graph, your task is to determine the shortest path between two specified nodes using the Floyd-Warshall algorithm. If there is no path between the start and destination nodes, output \(-1\). The algorithm computes the shortest distances between every pair of vertices in the graph using dynamic programming.

The input consists of multiple test cases. For each test case, you are given the number of nodes (intersections), the number of roads, the starting node, and the destination node, followed by the details of each road.

inputFormat

The first line of input contains an integer \(T\), the number of test cases. For each test case:

• The first line contains four integers: \(n\), \(m\), \(s\), and \(d\), where \(n\) is the number of intersections, \(m\) is the number of roads, \(s\) is the starting node, and \(d\) is the destination node.
• Each of the next \(m\) lines contains three integers: \(u\), \(v\), and \(w\), representing a road between intersections \(u\) and \(v\) with weight \(w\).

Note that each road is bidirectional.

outputFormat

For each test case, print the shortest distance from the starting node \(s\) to the destination node \(d\) on a new line. If no path exists, print \(-1\).

## sample

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

6
12
-1
0

</p>