Island Shortest Route

Initially, the islands are isolated without any routes. As development progresses, some bidirectional routes are added connecting two islands. A newly added route between island \( u \) and island \( v \) takes \( e \) time to travel. Hence, people can travel between these two islands with a travel time of \( e \). With the development of tourism, the shortest travel time between two islands becomes an important query.

Given a network of islands and routes, your task is to compute the shortest travel time between two specified islands. If there is no path connecting them, output \(-1\).

Input Format: The first line contains two integers \( n \) and \( m \), where \( n \) is the number of islands (numbered from 1 to \( n \)) and \( m \) is the number of routes. Following this, there are \( m \) lines, each containing three integers \( u \), \( v \), and \( e \), indicating that there is a bidirectional route between island \( u \) and island \( v \) with a travel time of \( e \). The last line contains two integers \( s \) and \( t \), representing the starting and destination islands.

Output Format: Output a single integer, the shortest travel time from island \( s \) to island \( t \). If there is no such route, output \(-1\).

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \( n \) and \( m \) where \( 1 \leq n \leq 10^5 \) and \( 0 \leq m \leq 10^5 \).
2. The next \( m \) lines each contain three integers \( u \), \( v \), and \( e \) (\( 1 \leq u, v \leq n \), \( 0 \leq e \leq 10^9 \)), representing a bidirectional route between island \( u \) and island \( v \) with a travel time of \( e \).
3. The last line contains two integers \( s \) and \( t \) (\( 1 \leq s, t \leq n \)), the starting and destination islands.

outputFormat

Output a single integer: the shortest travel time from island \( s \) to island \( t \). If no path exists, output \(-1\).

sample

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

9