4235. wxsの小图论

【题目背景】

zhdhttps://www.luogu.com.cn/user/1144284同学最近学习了非常简单的最短路算法，每 AC 一题就会用手十分大力的攻击他的同桌 wxs 同学，这一天，zhd 同学又大喊一声“You did it !!!”，并且顺手攻击了 wxs，wxs 非常愤怒，一怒之下出了一道小绿题板子攻击 zhd，由于 zhd 是个蒟蒻，并不会此题，于是让你来帮助 ta。

【题目描述】

给定 $n$ 个点，并给出 $m$ 条无向边（不排除重边的可能），每条边都有一定的权值。给出一个数 $k$，表示至多有多少条边可以使其权值置为 $0$。给出 $s, t$ 分别表示最短路的起点和终点，求出此路的最小权值为多少。

【输入格式】

第一行三个整数 $n, m, k$，分别表示图的点数，边数与至多有多少条边可以使其权值置为 $0$。 第二行两个整数 $s, t$，分别表示所求最短路的起点与终点。 接下来 $m$ 行，每行三个整数 $a, b, c$，表示 $a$ 到 $b$ 有一条边，权值为 $c$。

【输出格式】

输出一行一个整数，为最少花费。

【样例输入】

5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

【样例输出】

8

【样例说明】

无

【数据规模与约定】

对于 $30\%$ 的数据，$2 \le n \le 50$，$1 \le m \le 300$，$k=0$。

对于 $50\%$ 的数据，$2 \le n \le 600$，$1 \le m \le 6 \times 10^3$，$0 \le k \le 1$。 

对于 $100\%$ 的数据，$2 \le n \le 10^4$，$1 \le m \le 5 \times 10^4$，$0 \le k \le 10$，$0 \le s,t,a,b < n$，$a \neq b$。