Shortest Path in a Weighted Directed Graph

You are given a weighted directed graph with n nodes and m edges. Your task is to compute the shortest travel time from a given starting node s to a destination node t.

The graph is defined as follows:

• Nodes: 1, 2, …, n
• Edges: Each edge is a directed connection from node u to node v with an associated travel time w.

You can use Dijkstra’s algorithm to solve the problem. In particular, for every vertex v adjacent to an explored vertex u, update its tentative distance using:

If there is no route from s to t, output NO PATH.

The input and output are processed via standard input (stdin) and standard output (stdout).

inputFormat

The input begins with 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 t, where:

• n: number of nodes (junctions).
• m: number of edges (road segments).
• s: starting node index.
• t: destination node index.

Then m lines follow, each containing three integers u, v, and w, representing a directed road segment from node u to node v with travel time w.

All input is provided via stdin.

outputFormat

For each test case, output a single line containing the minimum travel time from s to t. If there is no available path, print NO PATH.

All output should be sent to stdout.## sample

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

16