Fastest Delivery Route

You are given a city represented as an undirected graph with n intersections and m roads. Each road connects two intersections with a travel time.

Your task is to find the shortest possible delivery time from a specified starting intersection to a destination intersection. Use Dijkstra's algorithm to determine the minimum travel time.

Formally, given an undirected graph \(G=(V,E)\) where each edge \((u,v)\) has weight \(w\) (the travel time), compute the minimum value of:

[ \text{Time} = \min_{\text{paths } P: start \to destination} \sum_{(u,v) \in P} w(u,v) ]

If the starting point is the same as the destination, the answer is zero.

inputFormat

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

n m
u1 v1 w1
u2 v2 w2
... (m lines total)
start destination

Where:

• n is the number of intersections.
• m is the number of roads.
• Each of the next m lines contains three integers u, v, and w representing a road between intersections u and v with travel time w.
• The last line contains two integers: the start intersection and the destination intersection.

outputFormat

Output a single integer to stdout — the minimum travel time required to reach the destination from the start.

## sample

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

4