Shortest Path in a Graph

You are given a weighted undirected graph representing a network of cities and roads. The first city is designated as the capital, and you are tasked with finding the shortest travel time from the capital to a target city. Roads represent bidirectional connections with associated travel times. If the target city is unreachable from the capital, output -1.

The problem can be formalized as follows:

Given:

• N: the number of cities, numbered from 1 to N.
• M: the number of roads connecting the cities.
• K: the target city number.
• C: the capital city number.
• A list of M roads, each represented by a tuple (u, v, w) indicating that city u and city v are connected by a road that takes time w to travel.

Your task is to compute the shortest travel time from city C to city K using Dijkstra's algorithm. If no path exists, return -1.

The mathematical formulation using Dijkstra's algorithm can be written in LaTeX as follows:

$$\text{Initialize } d(i)=\infty \text{ for all } i\in\{1,\ldots,N\}, \quad d(C)=0 $$$$\text{For each edge } (u,v,w): \text{ update } d(v) = \min(d(v), d(u)+w) \text{ and } d(u)=\min(d(u), d(v)+w) $$

Continue this process until the shortest distances for all cities are determined. Output the value d(K) if finite; otherwise, output -1.

inputFormat

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

N M K C
u1 v1 w1
u2 v2 w2
... 
up vp wp

Where:

• N is the number of cities.
• M is the number of roads.
• K is the target city.
• C is the capital city.
• Each of the next M lines contains three integers u, v, and w, representing a bidirectional road between cities u and v with a travel time of w.

outputFormat

The output is a single integer printed to stdout representing the shortest travel time from the capital city to the target city. If the target city is unreachable, output -1.

## sample

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

6