The Toll Roads Challenge

In this problem, a network of wonderful toll roads has been constructed in the European part of Russia for the World Programming Cup \(2112\). The network is comprised of \(m\) bidirectional toll roads connecting \(n\) cities. Each road connects two distinct cities, no two roads connect the same pair of cities, and it is possible to travel between any two cities using only these roads. In addition, no two roads intersect outside of the cities.

Each road is assigned a positive cost. Normally, the cost of a journey is the sum of the costs of all toll roads used. However, to boost travel between the two capitals (Saint Petersburg and Moscow), the company Radishchev Inc. offers a special deal: when traveling from Saint Petersburg to Moscow, the driver only pays for the \(k\) most expensive roads along his path.

Formally, consider a path consisting of \(l\) roads. Let \(c_{1}\) be the largest cost, \(c_{2}\) the second largest, and so on, so that \(c_{1} \ge c_{2} \ge \cdots \ge c_{l}\). If \(l \le k\), then the driver pays \(\sum_{i=1}^{l} c_{i}\). If \(l > k\), then the driver pays \(\sum_{i=1}^{k} c_{i}\). As the chief analyst at Radishchev Inc., your task is to compute the cheapest journey from Saint Petersburg (city 1) to Moscow (city \(n\)).

Note: If \(k=0\), then the driver pays nothing.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) \( (1 \le n, m \le \text{small})\). Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) indicating that there is a bidirectional road connecting cities \(u\) and \(v\) with cost \(w\). It is guaranteed that the graph is connected and no two roads connect the same pair of cities. City 1 is Saint Petersburg and city \(n\) is Moscow.

outputFormat

Output a single integer: the minimum cost to travel from Saint Petersburg to Moscow under the special offer scheme.

sample

4 4 1
1 2 5
2 3 1
3 4 5
1 4 12

10