Shortest Travel Time Between Fulfillment Centers

You are given a set of fulfillment centers connected by expressways. Each expressway connects two centers and has an associated travel time (weight). The problem is to determine the shortest travel time between a starting fulfillment center s and a destination fulfillment center d.

The network of centers can be modeled as an undirected weighted graph \( G = (V, E) \), where \( V \) is the set of centers and \( E \) is the set of expressways. The task is to compute the minimum travel time from \( s \) to \( d \) using the given expressways.

You may use Dijkstra's algorithm to solve this problem efficiently. Recall that Dijkstra's algorithm computes the shortest paths from a source node \( s \) to all other nodes in \( G \) by iteratively relaxing the edges.

inputFormat

The input is given via standard input (stdin) in the following format:

N M
a1 b1 w1
a2 b2 w2
... 
 aM bM wM
s d

Where:

• N is the number of fulfillment centers (nodes).
• M is the number of expressways (edges).
• Each of the next M lines contains three integers \( a_i \), \( b_i \), and \( w_i \) representing an expressway between centers \( a_i \) and \( b_i \) with travel time \( w_i \).
• The last line contains two integers \( s \) and \( d \) representing the starting and destination centers respectively.

outputFormat

Output the shortest travel time from the starting fulfillment center to the destination fulfillment center. The output should be written to standard output (stdout) and consist of a single integer.

## sample

5 5
1 2 10
1 3 30
2 4 40
3 4 20
4 5 10
1 5

60

</p>