Minimal Travel Effort

In this problem, you are given a forest represented by clearings and bidirectional paths connecting them. Each path has an associated positive effort. Your task is to determine the minimal travel effort required to travel from a starting clearing s to a target clearing t using the available paths. If there is no possible route, output -1.

You can use Dijkstra's algorithm to solve this problem. The update formula in each relaxation step can be written in \( \LaTeX \) as:

\( distance[v] = \min(distance[v],\; distance[u] + w) \)

where \(w\) is the effort for the path from clearing \(u\) to clearing \(v\).

inputFormat

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

1. The first line contains two integers \(n\) and \(m\) representing the number of clearings and the number of paths respectively.
2. Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) which represent a bidirectional path between clearings \(u\) and \(v\) with an effort \(w\).
3. The last line contains two integers \(s\) and \(t\), the starting and the target clearing.

outputFormat

Output a single integer to standard output (stdout), which is the minimal travel effort from clearing \(s\) to clearing \(t\). If no such path exists, output -1.

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

6