Description

村子间的小路年久失修，为了保障村子之间的往来，$A$君决定带领大家修路。

村子可以看做是一个边带权的无向图$G$， $G$ 由 $n$ 个点与 $m$ 条边组成，图中的点从 $1 \sim n$ 进行编号。现在请你选择图中的一些边，使得 $\forall 1 \leq i \leq d$ , $i$ 号点和 $n - i + 1$号点可以通过你选择出的那些边连通，并且你要最小化选出的所有边的权值和。请你告诉$A$君这个最小权值和。

Input Format

第一行三个整数 $n$, $m$ , $d$ 表示图中的点数、边数与限制条件。

接下来 $m$ 行每行三个整数 $u_i$, $v_i$ , $w_i$ 表示一条连接 $(u_i, v_i)$ 的权值为叫的无向边。

Output Format

仅一行一个整数表示答案。若无解输出 $-1$ .

Sample

样例输入

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

样例输出

9

Hint

$20\%$ 的数据： $d \leq 2$, $n \leq 10$, $m \leq 20$

$40\%$ 的数据： $d \leq 3$, $n \leq 100$, $m \leq 1000$

$70\%$ 的数据： $d \leq 4$, $n \leq 1000$, $m \leq 1000$

$100\%$ 的数据： $1 \leq d \leq 4$, $2d \leq n \leq 10^4$, $0 \leq m \leq 10 ^ 4$, $1 \leq w_i \leq 1000$