F1，中文全称为一级方程式锦标赛，是最高级的方程式赛车比赛，现在你作为一名选手参加了一场F1的比赛，比较特殊地，本次比赛是在一个N个点M条边的无向图上举行的。

起点是S，终点是T，每条边长度为1公里，赛车每行驶1公里耗油1个单位，途中共有k个加油站，每经过加油站时，可以把油加满，但你的赛车设计顾问告诉你，油箱容量越大，赛车跑的就越慢。为了追求最快的速度，在能顺利到达终点，不会中途没油的前提下，你希望最小化油箱的容量（注意，虽然油箱变小可能导致路径变长，但我们只关心最小化的油箱）。

对于30%的数据，N<=200,M<=2000。

对于60%的数据，N<=1000,M<=10000。

对于100%的数据，1<=K,S,T<=N<=100000,1<=M<=150000,1<=T<=5。