#4774. 修路

题目描述

村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 G = (V, E)，

请选择一些边，使得1 <= i <= d， i号节点和 n - i + 1 号节点可以通过选中的边连通，最小化选中的所有边

的权值和。

输入格式

第一行三个整数 n, m，d,表示图的点数和边数。接下来的 m行，每行三个整数 ui, vi, wi，表示有一条 ui 与 vi

之间，权值为 wi 的无向边。

1 <= d <= 4

2d <= n <= 10^4

0 <= m <= 10^4

1 <= ui, vi <= n

1 <= wi <= 1000

输出格式

一行一个整数，表示答案，如果无解输出-1

样例

样例输入

10 20 1  

6 5 1  

6 9 4  

9 4 2  

9 4 10  

6 1 2  

2 3 6  

7 6 10  

5 7 1  

9 7 2  

5 9 10  

1 6 8  

4 7 4  

5 7 1  

2 6 9  

10 10 6  

8 7 2  

10 9 10  

1 2 4  

10 1 8  

9 9 7  

样例输出

8

数据范围与提示