A delivery company operates in a region with
A package starts at hub
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of hubs and the number of roads.
Each of the next KaTeX can only parse string typed expression lines contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression, meaning there is a two-way road between hubs KaTeX can only parse string typed expression and KaTeX can only parse string typed expression that takes KaTeX can only parse string typed expression units of time.
Print the minimum total time to travel from hub KaTeX can only parse string typed expression to hub KaTeX can only parse string typed expression. If it is not reachable, print KaTeX can only parse string typed expression.
Input
5 5
1 2 4
1 3 1
3 2 1
2 5 3
3 5 75The route KaTeX can only parse string typed expression costs KaTeX can only parse string typed expression, which is cheaper than KaTeX can only parse string typed expression (cost KaTeX can only parse string typed expression) or KaTeX can only parse string typed expression (cost KaTeX can only parse string typed expression).
Example 2:
Input
4 2
1 2 5
3 4 2-1Hub KaTeX can only parse string typed expression lies in a part of the network with no connection to hub KaTeX can only parse string typed expression, so it can never be reached.
Example 3:
Input
3 3
1 3 10
1 2 2
2 3 35Going directly costs KaTeX can only parse string typed expression, but the detour KaTeX can only parse string typed expression costs only KaTeX can only parse string typed expression.