Shortest Travel Time

You are given a network of cities connected by roads. Each road connects two cities and has an associated travel time. Your task is to compute the shortest travel time from city \( u \) to city \( v \). If there is no possible path between the two cities, output INF.

The problem can be formally stated as follows:

Given \( n \) cities and \( m \) roads, where each road is described by a tuple \( (c_1, c_2, t) \) indicating that there is a bidirectional road between city \( c_1 \) and city \( c_2 \) with travel time \( t \), find the minimum travel time required to go from city \( u \) to city \( v \). If there is no path, output "INF".

You may use Dijkstra's algorithm for an efficient solution. The typical recurrence for updating distances is:

[ dist[v] = \min(dist[v],, dist[u]+w(u,v)) ]

where \( w(u,v) \) is the travel time for the road connecting \( u \) and \( v \).

inputFormat

The input is read from stdin and consists of:

• The first line contains four integers: \( n \), \( m \), \( u \), and \( v \), where \( n \) is the number of cities, \( m \) is the number of roads, \( u \) is the start city, and \( v \) is the destination city.
• The next \( m \) lines each contain three integers \( c_1 \), \( c_2 \), and \( t \), which describe a bidirectional road between city \( c_1 \) and city \( c_2 \) with travel time \( t \).

All values are separated by spaces.

outputFormat

Output a single line to stdout containing the minimum travel time from city \( u \) to city \( v \). If city \( v \) cannot be reached from city \( u \), output INF.

## sample

4 4 1 4
1 2 4
2 3 1
3 4 3
1 3 2

5

</p>