题目描述

N 个城市，编号为 1 ~ N。

有 M 条无向道路将这些城市连通起来，每条道路都连接两个不同的城市，任意两个城市间最多只有一条道路直接相连。

经过每条道路需要花费一定的时间 Ti（所有 Ti 均为偶数）。

你现在正在城市 1，准备去城市 N。

你有 K 个加速器。

在任意一条道路上使用加速器，可以使得通过这条道路的时间减少一半。

一条道路最多只能使用一个加速器。一个加速器只能在一条道路上使用。你可以不使用完所有的加速器。

问：你完成行程最少需要花费多少时间？

输入格式

第一行：三个整数： $N$ 、 $M$ 、 $K$ 。

接下来 $M$ 行，每行三个整数： $U_i$ 、 $V_i$ 、 $T_i$ ，表示 $U_i$ 号城市与 $V_i$ 号城市之间的道路需要花费 $T_i$ 的时间。

一个整数，表示答案。

$30\%$ 的数据： $1 \leq K \leq N \leq 10$ ， $M \leq 10$ 。

$100\%$ 的数据： $1 \leq K \leq N \leq 50$ ， $M \leq 10^3$ ， $1 \leq U_i,V_i \leq N$ ， $2 \leq T_i \leq 2 \times 10^3$ 。