当前没有测试数据。

3.修建道路

题目描述

$sub$打算修建一条磁悬浮列车的通道连接现代$OI$王国的首都（编号为$1$）和$sub$的家（编号为$n$）。

当然，现代$OI$集团的$n$座城市之间没有任何的磁悬浮通道，而$sub$通过实地勘测发现，一共有$p$对城市之间可以建磁悬浮通道。

在这$p$对城市之中，第$i$对城市分别为$a_i$，$b_i$，它们间的距离为$l_i$。数据中保证每对$(a_i,b_i)$最多只出现$1$次，现代$OI$集团决定免费帮$sub$修建最多$k$条线路的磁悬浮通道，而$sub$要花的钱，是他自己负责修建的那些线路的最长的那条路的长度。

$sub$当然想花最少的钱，他想知道他最少能花多少钱。

输入格式

第$1$行输入$3$个整数：$n$，$p$，$k$。

第$2$行到第$p+1$行，其中第$i+1$行为$3$个用空格隔开的整数：$a_i$，$b_i$，$l_i$。

输出格式

输出$1$个整数，为$sub$在这项工程上的最小支出。如果任务不可能完成，输出$-1$。

数据范围与提示

对于$100\%$的数据，满足$1 \leq k \leq n \leq 10^{3}$，$1 \leq p \leq 10^{4}$，$1 \leq l_i \leq 10^{6}$。

样例

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

4

说明

现代$OI$集团一共有$5$个城市。城市$1$不能直接与城市$4$,$5$相连。城市$5$不能直接与城市$1$,$3$相连。其余所有城市间均可修建轨道。现代$OI$集团可以免费为$sub$修建一条线路。

$sub$选择如下的修建方案：$1 \to 3$，$3 \to 2$，$2 \to 5$，这$3$条路线的长度分别为$4$,$3$,$9$。$sub$让现代$OI$集团免费修建那条长度为$9$的路线，于是，他所需要花费的钱为$4$。