题目描述

陶渊明（365-427）是中国东晋时期的一位著名诗人。他最著名的著作之一是《桃花源记》，讲述了一个偶然发现的虚幻村庄的寓言故事，故事中的人们在与自然和谐共处，长久以来完全不知道外面世界的存在。所以在汉语中，“桃花源”代表着“乌托邦”。

在《桃花源记》的故事中，存在一个神秘的地方。在秦朝时期，一些人在乱世中逃到那个地方并建立了一个村庄。他们和他们的后代从未离开过，也从未与外界有过任何联系，直到几个世纪后晋朝的一个渔夫发现了他们。

最近，一些中国的ACMer偶然发现了《桃花源记》中提到的村庄的遗迹。

他们还发现了一份有关筑造藏身之处以逃避秦军的文件。文件中写道：

村庄中有 $n$ 栋房子和 $m$ 条道路。每条道路连接两栋房子。这些房子从 $1$ 号到 $n$ 号进行编号。有 $k$ 个家庭，每个家庭住在不同的房子里。

他们住的房子分别是 $1$ 号、$2$ 号，…，$k$ 号房子。还有 $k$ 户空房子：$n-k+1$ 号、$n-k+2$ 号，…，$n$ 号房子下面有地下室，这样这些房子可以被用作藏身之处。

问题是所有的道路都已经断裂了。人们想要修复一些道路，以便每个家庭能够通过修好的道路到达藏身之处。每个藏身之处只能容纳一个家庭。每条道路修复的花费各不相同。村庄的首领想要找到修路的最小花费方法，但他不知道应该怎么做。

你能解决古老村庄首领没有解决的问题吗？

输入格式

第一行以三个整数开头——上面提到的 $n, m$ 和 $k$。然后，$m$ 行跟着，每行包含三个整数 $u, v$ 和 $w$，表示一条连接 $u$ 号房子和 $v$ 号房子的断裂的道路，修复这条道路的花费是 $w$。

输出格式

如果你找不到一个合适的修路方案，输出 $-1$。否则，在一行中输出修复道路的最小花费。

输入样例

4 3 1
4 2 10
3 1 9
2 3 10

输出样例

29

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 7\times 10^3$，$0\le m\le 10^4$，$1\le k\le 5$，$2k\le n$，$1\le w\le 10^3$。