Internet Installation

Computers are numbered from 1 to N. Initially, no computers are connected, but P candidate cables are given. Each candidate connects two computers and has an installation cost.

Computer 1 is already directly connected to the internet server. Your goal is to make computer N connected to computer 1 through installed cables. It does not matter whether any other computers are connected.

Up to K of the installed cables can be installed for free. For the remaining installed cables, only the most expensive one among them is charged. Determine the minimum amount that must be paid to achieve the goal.

The first line contains the number of computers N(1 ≤ N ≤ 1,000), the number of candidate cables P(1 ≤ P ≤ 10,000), and the number of cables that can be installed for free K(0 ≤ K < N).

Each of the next P lines contains the two computer numbers connected by a cable and that cable's installation cost. Each cost is between 1 and 1,000,000, inclusive.

Print the minimum amount that must be paid to connect computer 1 and computer N. If they cannot be connected, print -1.

If the path 1-3, 3-2, 2-5 is used, the cable costs are 4, 3, and 9.

Since 1 cable can be installed for free, the cable with cost 9 can be made free. The most expensive remaining cable costs 4, so the paid amount is 4.