[Usaco2007 Jan]Telephone Lines架设电话线

农场主 John 打算将电话线接入自己的农场，但电信公司并不提供免费服务，因此他需要支付一定的费用。

农场周围有 $N$ 根废弃的电话线杆，依次编号为 $1$ 到 $N$ ，目前任意两根电话线杆之间都没有电话线相连。其中有 $P$ 对电话线杆可以架设电话线，其余电话线杆之间由于距离过远而无法连接。

第 $i$ 对可以连接的电话线杆分别为 $A_i$ 和 $B_i$ ，架设在它们之间的电话线长度为 $L_i$ 。每一对无序点对 $\{A_i,B_i\}$ 在数据中最多出现 $1$ 次。

编号为 $1$ 的电话线杆已经接入全国电话网络，农场中的电话线路最终需要连接到编号为 $N$ 的电话线杆。因此，只需选择一条连接电话线杆 $1$ 与电话线杆 $N$ 的路径，其他电话线杆不一定需要接入电话网络。

经过协商，电信公司同意免费架设其中由 John 指定的 $K$ 条电话线。对于其余需要付费的电话线，John 支付的总费用等于这些电话线中最长一条的长度。如果所选路径需要架设的电话线不超过 $K$ 条，则总费用为 $0$ 。

请计算 John 架设电话线所需支付的最少费用。

输入格式

第一行包含三个以空格分隔的整数 $N$ 、 $P$ 和 $K$ ，分别表示电话线杆数量、可以架设电话线的电话线杆对数，以及可以免费架设的电话线数量。

接下来 $P$ 行，第 $i$ 行包含三个以空格分隔的整数 $A_i$ 、 $B_i$ 和 $L_i$ ，表示可以在电话线杆 $A_i$ 与 $B_i$ 之间架设一条长度为 $L_i$ 的电话线。

输出一个整数，表示 John 需要支付的最少费用。

如果无法连接电话线杆 $1$ 与电话线杆 $N$ ，输出 $-1$ 。

可以选择路径 $1\to 3\to 2\to 5$ ，其中各条电话线的长度依次为 $4$ 、 $3$ 和 $9$ 。让电信公司免费架设长度为 $9$ 的电话线后，剩余电话线中的最大长度为 $4$ ，因此最少费用为 $4$ 。

本题为 USACO 2007 January 试题「Telephone Lines（架设电话线）」，题面与测试数据整理自 BZOJ。