Shortest Path in the Cave Network

You are given a network of caves connected by bidirectional tunnels. Each tunnel connects two caves and has an associated length. Your task is to find the shortest path between a given start cave S and a target cave T. If no path exists, output "NO PATH".

The problem can be formulated as follows: Given a graph \(G=(V, E)\) where \(|V| = N\) represents the caves and \(|E| = M\) represents the tunnels. Each edge is represented by a triple \((u, v, l)\) which indicates that cave \(u\) and cave \(v\) are connected by a tunnel of length \(l\). Using algorithms such as Dijkstra's algorithm, determine the minimum distance from \(S\) to \(T\). In case there is no feasible path, output "NO PATH".

inputFormat

The input is read from standard input and has the following format:

N M
u1 v1 l1
u2 v2 l2
... (M lines total)
S T

Where:

• N is the number of caves (nodes).
• M is the number of tunnels (edges).
• Each of the next M lines contains three integers \(u\), \(v\), and \(l\), indicating a tunnel between caves \(u\) and \(v\) with length \(l\).
• The last line contains two integers \(S\) and \(T\), which are the starting and target caves respectively.

outputFormat

Print a single line to standard output representing the length of the shortest path between cave S and cave T. If no such path exists, output "NO PATH".

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

9