琳琳和兰兰在五一节假日期间去旅游，他们计划乘飞机旅行，选择了一家相对便宜的航空公司。该航空公司一共在n个城市开通航线，设这些城市分别标记为0到n-1，一共有m条航线，每条航线连接两个城市，并且每条航线的价格不同。</br. 琳琳和兰兰现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费乘坐k次。那么琳琳和兰兰这次出行最少花费多少？

第一行三个整数n,m,k分别表示城市数，航线数和免费乘坐次数。 接下来一行两个整数s,t分别表示他们出行的起点城市编号和终点城市编号。 接下来 m行，每行三个整数a,b,c表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。

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

【数据范围】