Shortest Travel Time

We are given a weighted undirected graph representing intersections and roads with travel times. For each test case, determine the shortest travel time between a given source and destination intersection. If there is no valid path, output no path.

The problem can be formulated as follows:

$$ \min_{path \in \mathcal{P}(s,d)} \sum_{(u,v) \in path} t_{uv} $$

Design an efficient algorithm to solve the problem.

inputFormat

The input is given via standard input and follows the format below:

• The first line contains an integer T, the number of test cases.
• For each test case:
  1. The first line contains two integers n and m, representing the number of intersections and roads, respectively.
  2. The next m lines each contain three integers u, v, and t, indicating a bidirectional road between intersections u and v with travel time t.
  3. The last line of each test case contains two integers s and d, the source and destination intersections.

outputFormat

For each test case, output a single line containing the shortest travel time from s to d. If no path exists, output no path (without quotes).

1
4 4
1 2 10
1 3 15
2 4 10
3 4 5
1 4

20