P1948 [USACO08JAN] Telephone Lines S

Farmer John 想在自己的农场架设一条电话线。不幸的是，电话公司并不配合，所以他只能自己承担一部分连接农场与电话系统所需的电缆费用。 有 $N$（$1 \le N \le 1{,}000$）根孤立的电线杆散布在农场各处，为方便起见，这些电线杆被编号为 $1 \ldots N$；它们之间没有任何电缆连接。共有 $P$（$1 \le P \le 10{,}000$）对电线杆可以用电缆连接，其余的电线杆对相距太远。 第 $i$ 根电缆可以连接两个不同的电线杆 $A_i$ 和 $B_i$，长度为 $L_i$（$1 \le L_i \le 1{,}000{,}000$）单位（输入中不存在重复的 $\{A_i, B_i\}$ 对）。电线杆 $1$ 已经接入电话系统，电线杆 $N$ 位于农场。需要用一条由电缆组成的路径把电线杆 $1$ 和 $N$ 连通，其余的电线杆用或不用都可以。 电话公司愿意免费为 Farmer John 提供 $K$（$0 \le K < N$）段电缆。除这 $K$ 段外，他需要的其余电缆按其中最长的长度计费（每对电线杆之间的连接各用一根独立的电缆）；如果他不需要任何额外的电缆，则支付 $0$。 求 Farmer John 至少需要支付多少钱。

第一行输入三个整数 $N,P,K$。 接下来 $P$ 行，第 $i$ 行包含三个整数 $A_i,B_i,L_i$。

一行一个整数，表示 Farmer John 至少要付的金额。如果无法把农场接到电话系统上，输出 `-1`。