Fastest Journey with SpellCards

You are given a continent with N cities numbered from \(1\) to \(N\) and M bidirectional roads. You start at city \(1\) and wish to reach city \(N\) in the shortest possible time.

Each road has an associated travel time. In addition, you have \(K\) SpellCards. When traversing a road, you can choose to use a SpellCard which will reduce the travel time on that road to \(\frac{1}{2}\) of its original value. Note that:

1. You can use at most one SpellCard on any single road.
2. Each SpellCard affects only one road.
3. You do not have to use all SpellCards.

Your task is to determine the minimum time required to travel from city \(1\) to city \(N\) when you can use at most \(K\) SpellCards.

This is a classic shortest path problem with an extra state dimension for SpellCard usage. Algorithms such as Dijkstra's algorithm can be applied with state expansion.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\) where \(N\) is the number of cities, \(M\) is the number of roads, and \(K\) is the number of SpellCards available.

Each of the following \(M\) lines contains three numbers \(u\), \(v\), and \(w\), indicating that there is a bidirectional road between city \(u\) and city \(v\) with travel time \(w\).

outputFormat

Output a single number representing the minimum travel time from city \(1\) to city \(N\). If the answer is an integer, output it without decimal places; otherwise, output the floating point value.

sample

3 3 1
1 2 10
2 3 10
1 3 100

15