只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
4774 - 修路
村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 G = (V, E)， 请选择一些边，使得1 <= i <= d， i号节点和 n - i + 1 号节点可以通过选中的边连通，最小化选中的所有边 的权值和。
Input
第一行两个整数 n, m，表示图的点数和边数。接下来的 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
Output
一行一个整数，表示答案，如果无解输出-1
Examples
Input
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
Output
8