Minimum Cost Flight Journey with Free Coupons

Alice and Bob are about to travel by plane. They have chosen a relatively cheap airline which operates in \(n\) cities labeled from \(0\) to \(n-1\) and offers \(m\) flights between these cities. Each flight connects two cities and has an associated cost.

As a special promotion, the airline offers a discount: Alice and Bob can enjoy up to \(k\) flights for free (i.e. the cost of those flights will be waived). They can use these free flights on any legs of their journey.

The task is to determine the minimum total cost to travel from a given starting city \(s\) to a destination city \(t\), taking advantage of the free flights if beneficial. If there is no route from \(s\) to \(t\), output \(-1\).

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) where:

• \(n\) is the number of cities (labeled from \(0\) to \(n-1\)).
• \(m\) is the number of flights.
• \(k\) is the maximum number of flights that can be taken for free.

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(c\) representing a flight between city \(u\) and city \(v\) with cost \(c\). It is assumed that the flights are bidirectional.

The last line contains two integers \(s\) and \(t\), the starting city and the destination city respectively.

outputFormat

Output a single integer representing the minimum cost to travel from the starting city \(s\) to the destination city \(t\). If there is no valid route, output \(-1\).

sample

4 4 1
0 1 100
1 2 200
2 3 300
0 3 1000
0 3

0