农夫约翰每天都会认真检查他的奶牛。他会穿越一些编号为 1 到 M 的小径（1 \leq M \leq 50,000），从牧场 1 一直走到牧场 N（对于测试数据给出的路径图，这段旅程总是可能的）。农夫约翰的农场上有 N 个牧场（1 \leq N \leq 10,000），它们通过双向泥土小径连接在一起。每条小径 i 连接牧场 P1_i 和 P2_i（1 \leq P1_i \leq N,1 \leq P2_i \leq N），需要 T_i（1 \leq T_i \leq 10^6）单位时间来穿越。
他想要改造农场上的一些小径，以节省长途旅行的时间。具体来说，他将选择 K（1 \leq K \leq 20）条小径将其改造成高速公路，这将有效地将小径的穿越时间减少到 0。帮助 FJ 决定改造哪些小径以最小化从牧场 1 到 N 的最终时间。
第 1 行：三个用空格分隔的整数：N,M 和 K。
第 2 行到第 M+1 行：第 i+1 行描述小径 i，包含三个用空格分隔的整数：P1_i、P2_i 和 T_i。
共 1 行：改造不超过 K 条边后的最短路径长度。
4 4 1 1 2 10 2 4 10 1 3 1 3 4 100
1
K 为 1；将小径 3 \to 4 改造成高速公路，时间从 100 变为 0。新的最短路径为 1 \to 3 \to 4，总穿越时间现在为 1。