Shortest Travel Time Between Cities

You are given a network of cities and bidirectional trains connecting them. Each train connects two cities and takes a specified amount of time to travel. Your task is to determine the shortest possible travel time from a starting city S to a destination city T.

The network is described by:

• N: the number of cities (cities are numbered from 1 to N).
• K: the number of train routes.
• S: the starting city number.
• T: the destination city number.
• A list of K trains, each represented by three integers \(A_i\), \(B_i\), and \(T_i\). This means there is a train between city \(A_i\) and city \(B_i\) with travel time \(T_i\). The travel is bidirectional.

If there is no valid route from city S to city T, output -1. Note that if S and T are the same city, the minimum travel time is 0.

This problem can be modeled using a weighted undirected graph and solved with Dijkstra's algorithm. The recurrence relation in Dijkstra's algorithm can be summarized as:

[ d[u] = \min_{(u,v) \in E} { d[v] + w(u,v) } ]

Where \(d[u]\) is the shortest distance from the source S to vertex u, and \(w(u,v)\) is the weight of the edge between u and v.

inputFormat

The input is read from stdin and has the following format:

N K S T
A1 B1 T1
A2 B2 T2
... 
AK BK TK

Where:

• The first line contains four space-separated integers: N (number of cities), K (number of trains), S (starting city), and T (destination city).
• The next K lines each contain three space-separated integers: Ai, Bi, and Ti representing a train route.

outputFormat

Output a single integer to stdout: the shortest travel time from city S to city T. If there is no route that connects S and T, output -1.

## sample

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

10