Minimum Cost Through an Intermediate City

You are given a network of n cities connected by m bidirectional highways. Each highway has an associated travel cost. Your task is to find the minimum travel cost to go from city 1 to city n such that the journey passes through a specific intermediate city k. If there is no valid path, output -1.

The problem can be modeled as a graph problem. Use Dijkstra's algorithm (or any other appropriate algorithm) to compute the shortest path from city 1 to city k and from city k to city n, then output the sum of these two distances. Make sure to handle graphs where some cities are unreachable.

The formula used in solving this problem can be represented as:

[ \text{answer} = d(1,k) + d(k,n), ]

where \(d(x,y)\) represents the minimum distance between cities \(x\) and \(y\). If either \(d(1,k)\) or \(d(k,n)\) is infinity (i.e. no possible path exists), then the output should be -1.

inputFormat

The first line of input contains three integers: n (the number of cities), m (the number of highways), and k (the intermediate city that must be visited).

This is followed by m lines, each containing three integers u v w, where there is a bidirectional highway between city u and city v with travel cost w.

outputFormat

Output a single integer which is the minimum travel cost from city 1 to city n via city k. If no valid path exists, output -1.## sample

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

10