折扣路线（route）

题目描述

$\text{DAMON THRONE}$ 的训练队要从城市 $S$ 前往城市 $T$。

有 $n$ 个城市，$m$ 条双向道路。第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$，通过这条道路需要花费 $w_i$ 点能量。

训练队拥有 $K$ 张折扣卡。每张折扣卡可以在经过一条道路时使用一次，使这条道路的能量花费变为：

$$\left\lfloor \frac{w_i}{2} \right\rfloor$$

每条道路可以多次经过，但每次经过时最多使用一张折扣卡。所有折扣卡总共最多使用 $K$ 次，也可以不全部使用。

请你求出从城市 $S$ 到城市 $T$ 的最小能量花费。

如果无法从 $S$ 到达 $T$，输出 $-1$。

输入格式

第一行包含五个整数 $n,m,K,S,T$，分别表示城市数量、道路数量、折扣卡数量、起点城市和终点城市。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示一条双向道路。

输出格式

输出一行一个整数。

如果可以从 $S$ 到达 $T$，输出最小能量花费；否则输出 $-1$。

输入输出样例 #1

输入 #1

5 6 1 1 5
1 2 8
2 5 8
1 3 5
3 4 5
4 5 5
2 3 2

输出 #1

11

样例解释 #1

一种最优方案为：

从 $1$ 到 $3$，使用折扣卡，花费：

$$\left\lfloor \frac{5}{2} \right\rfloor=2$$

然后从 $3$ 到 $4$，花费 $5$。

再从 $4$ 到 $5$，花费 $5$。

总花费为：

$$2+5+5=12$$

输入输出样例 #2

输入 #2

4 2 2 1 4
1 2 10
2 3 10

输出 #2

-1

数据范围与约定

对于所有测试数据，保证：

$$1 \le n \le 2\times 10^5,\quad 0 \le m \le 2\times 10^5,\quad 0 \le K \le 10,\quad 1 \le S,T \le n,\quad 1 \le w_i \le 10^9 $$$$1 \le u_i,v_i \le n,\quad u_i\ne v_i$$

测试点	分值	$n$	$m$	$K$	特殊性质
$1\sim 2$	$10$	$\le 20$	$\le 100$	$\le 1$	无
$3\sim 4$	$20$	$\le 2000$	$\le 5000$	$=0$	$\text{A}$
$5\sim 6$				$\le 10$	无
$7\sim 8$		$\le 10^5$		$\le 1$	$\text{B}$
$9\sim 10$	$30$	$\le 2\times 10^5$		$\le 10$	无

特殊性质 $\text{A}$：保证 $K=0$，即不能使用折扣卡。

特殊性质 $\text{B}$：保证 $K\le1$。