Shortest Path in a Directed Graph

In this problem, you are given a directed graph with weighted edges. Your task is to compute the shortest path from a given source vertex S to a destination vertex D for each test case using Dijkstra's algorithm. If there is no path from S to D, output -1.

The problem can be formulated as follows: Given a directed graph $G=(V,E)$ with $N$ vertices and $M$ edges, and two vertices $S$ and $D$, find the minimum distance from $S$ to $D$. If no such path exists, print -1.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer T, the number of test cases. Each test case is described as follows:

- The first line of each test case contains four integers: N, M, S, and D, where N is the number of vertices, M is the number of edges, S is the source vertex, and D is the destination vertex.
- The next M lines each contain three integers u, v, and w, representing a directed edge from u to v with weight w.

outputFormat

For each test case, output a single line on standard output (stdout) containing one integer: the shortest path distance from S to D. If there is no path from S to D, output -1.## sample

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

6