Map data from OpenStreetMap, available under the Open Database License (ODbL).
As you board the train, a song is stuck in your head, about a small-town girl and a city boy, taking the midnight train goin' anywhere. You, alas, are going somewhere. Your stingy employer is sending you to a conference, and will reimburse your travel expenses—or rather, some of them. Under the company's reimbursement policy, only the $$$k$$$ cheapest legs of your journey are paid for; the rest comes out of your own pocket.
The railroad network consists of stations connected by legs, each of which goes from one station to another for some particular price. There may or may not be a leg going the opposite way, and if there is, it might be priced differently. Plan a journey from your home station to the conference station that minimizes what you pay yourself: the total price of all its legs except the $$$k$$$ cheapest (or nothing at all, if the journey has at most $$$k$$$ legs).
The input consists of:
- One line with three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n \leq 2000$$$, $$$1 \leq m \leq 3000$$$, $$$0 \leq k \leq 3000$$$), the number of stations, the number of legs, and the number of legs that are reimbursed.
- $$$m$$$ lines, each containing three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$0 \leq u, v \lt n$$$, $$$1 \leq w \leq 10^5$$$, $$$u \neq v$$$), a leg from station $$$u$$$ to station $$$v$$$ at cost $$$w$$$.
Output the minimum amount you have to pay yourself for a journey from station $$$0$$$ to station $$$n-1$$$.
4 3 10 1 121 2 112 3 30
42
6 6 10 1 11 2 42 5 40 3 33 4 34 5 4
7
7 9 20 1 70 2 31 2 51 3 13 4 31 4 42 5 25 4 94 6 8
8
7 9 10 1 70 2 31 2 51 3 13 4 31 4 42 5 25 4 94 6 8
15
