Wizard Maze Rescue

Wizard Xiao Lan embarks on a dangerous journey through an enemy‐set magical maze in order to rescue his friend Xiao Q. The magical maze is represented as an undirected graph with \(N\) nodes (numbered \(0,1,2,\dots,N-1\)) and \(M\) edges. There are no multiple edges or self-loops. Each edge in the graph has an associated damage value \(w\), and every time Xiao Lan traverses an edge, he incurs that amount of damage.

Xiao Lan starts at node \(0\) and wishes to reach node \(N-1\). Moreover, he has a special spell. Suppose he travels along a path and the sequence of edges taken is \(e_1, e_2, \dots, e_L\) (edges may be repeated). Normally, the total damage inflicted is \[ P = \sum_{i=1}^{L} w(e_i), \] where \(w(e_i)\) is the damage of edge \(e_i\). However, if \(L \ge K\), he may choose exactly one consecutive segment of \(K\) edges, say \(e_c, e_{c+1}, \dots, e_{c+K-1}\), and completely avoid the damage from these \(K\) edges. That is, the total damage becomes \[ P' = P - \sum_{i=c}^{c+K-1} w(e_i). \]

The spell can be used at most once; if \(L < K\), the spell cannot be used. Determine the minimum possible total damage Xiao Lan can incur while traveling from node \(0\) to node \(N-1\). It is guaranteed that at least one valid path exists.

inputFormat

The first line contains three integers \(N\), \(M\) and \(K\) separated by spaces.

Then follow \(M\) lines, each containing three integers \(u\), \(v\) and \(w\), describing an undirected edge between nodes \(u\) and \(v\) with a damage value of \(w\).

\(0 \le u, v \le N-1\); the graph has no self-loops or multiple edges.

outputFormat

Output a single integer, the minimum total damage Xiao Lan can receive on his journey from node \(0\) to node \(N-1\).

sample

4 4 2
0 1 5
1 3 10
0 2 2
2 3 2

0