4235. wxsの小图论

【题目背景】

zhdhttp:////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≤n≤50,1≤m≤300,k=0。 

对于 50% 的数据， 2≤n≤600,1≤m≤6×10^3,0≤k≤1。 

对于 100% 的数据， 2≤n≤10^4,1≤m≤5×10^4,0≤k≤10,0≤s,t,a,b<n ，a!=b。