Shortest Travel Time in Island Network

You are given a network of N islands connected by K bidirectional portals. Each portal connects two islands and has an associated travel time. The islands are numbered from 1 to N. Given the starting island S and the destination island D, your task is to compute the shortest travel time from S to D using these portals. If there is no valid route between the two islands, output -1.

The travel time through a portal is a positive integer. In some cases, the starting and destination islands might be the same, in which case the answer is 0.

The problem can be formally described by the following formula for the travel time along a path:

\( T_{total} = \sum_{i=1}^{m} t_i \)

where \( t_i \) is the travel time of the \( i^{th} \) portal in the chosen route and \( m \) is the number of portals used.

inputFormat

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

N K
u1 v1 t1
nu2 v2 t2
...
nuK vK tK
S D

Here,

• N: Number of islands.
• K: Number of portals.
• Each of the next K lines contains three integers: u, v and t representing a portal connecting island u and island v with travel time t.
• The last line contains two integers: S (starting island) and D (destination island).

outputFormat

Output a single integer to standard output representing the shortest travel time from island S to island D. If there is no path connecting S and D, output -1.

## sample

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

15