题目描述

村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 $G = (V, E)$，请选择一些边，使得 $1\le i \le d$，$i$ 号节点和 $n - i + 1$ 号节点可以通过选中的边连通，最小化选中的所有边的权值和。

输入格式

第一行两个整数 $n, m$，表示图的点数和边数。接下来的 $m$ 行，每行三个整数 $u_i, v_i, w_i$，表示有一条 $u_i$ 与 $v_i$ 之间，权值为 $w_i$ 的无向边。

输出格式

一行一个整数，表示答案，如果无解输出 -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

数据规模与约定

对于 $100\%$ 的数据，$1 \le d \le 4$，$2d \le n \le 10^4$，$0 \le m \le 10^4$，$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^3$。