题目描述
有 $n$ 个城市（编号为 $0 \cdots n-1$ ），$m$ 条道路，经过每条道路有一个花费 $v$ 。特别的是，现在可以让其中的最多 $k$ 个道路花费为 $0$ 。从城市 $s$ 到城市 $t$ ，求最小花费。
输入
第一行，三个整数 $n,m,k$ 如题意所描述。
第二行，两个整数 $s,t$ 代表出发城市和目标城市编号。
接下来 $m$ 行，每行三个整数 $x,y,v$ 代表 $x$ 和 $y$ 城市之间的高速公路收费为 $v$ 元。
输出
共一行，输出一个整数，代表最少花费。
样例输入输出
输入#1
复制
5 6 1
0 4
2 3 5
0 1 15
1 2 5
3 4 5
2 3 3
0 2 1005
输入#2
复制
4 3 1
1 3
0 1 50
1 2 30
1 3 50
提示
对于 $10\%$ 的数据，$n \leq 100$，$k=0$；
对于 $30\%$ 的数据，$n \leq 5$，$m \leq 10$ ，$k \leq 2$；
对于 $100\%$ 的数据，$n \leq 1000$，$m \leq 50000$ ，$k \leq 10$；$v \leq 10000$。