Shortest Travel Time

Given a directed graph with \(N\) nodes and \(M\) edges where each edge has a positive travel time, your task is to determine the shortest travel time between two given nodes \(S\) and \(T\). If there is no feasible path, output \(-1\). The graph is represented using a list of roads, where each road from node \(u\) to node \(v\) has a travel time \(w\). Note that when \(S = T\), the travel time is \(0\).

Constraints: The travel times are positive integers. The nodes are numbered from 1 to \(N\). Your solution is expected to run efficiently on moderately sized graphs using algorithms such as Dijkstra's algorithm.

inputFormat

The input is given from stdin and has the following format:

N M
u1 v1 w1
u2 v2 w2
...
uM vM wM
S T

where:

• N and M are the number of nodes and edges respectively.
• Each of the next M lines contains three integers \(u\), \(v\), \(w\) representing a directed road from node \(u\) to node \(v\) with travel time \(w\).
• The last line contains two integers \(S\) and \(T\), the starting and destination nodes respectively.

outputFormat

Print the shortest travel time from node \(S\) to node \(T\) on stdout. If no valid path exists, print \(-1\).

## sample

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

6

</p>