Taco Treasure Hunt

You are given a directed graph representing rooms and one-way passageways. Each edge in the graph has a positive length that represents the distance between two rooms. Your task is to find the shortest distance from a start room to a treasure room using the available passageways.

Mathematically, if \(\mathcal{P}\) is the set of all paths from the start to the treasure room and \(w(e)\) is the weight of edge \(e\), then the answer is computed as:

[ \min_{P \in \mathcal{P}} \sum_{e \in P} w(e) ]

If there is no valid path, output -1. Note that if the start and treasure rooms are the same, the answer is 0.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(T\) (the number of test cases). Each test case consists of the following lines:

• The first line of each test case contains two integers \(m\) and \(n\), where \(m\) is the number of rooms and \(n\) is the number of one-way passageways.
• The next \(n\) lines each contain three integers \(u\), \(v\), and \(l\) indicating there is a directed edge from room \(u\) to room \(v\) with length \(l\).
• The last line of each test case contains two integers representing the start room and the treasure room.

Constraints: \(1 \le m \le 10^5\) (depending on the dataset) and all lengths are positive integers.

outputFormat

For each test case, print a single line with one integer — the length of the shortest path from the start room to the treasure room, or -1 if no such path exists. The output should be printed to standard output (stdout).

## sample

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

8
7
-1
0

</p>