愿时间过得慢一些，让我记住他的一颦一笑——DongDong DongDong家的萨摩耶去国外读书了，DongDong非常想他，决定假期坐飞机去看望他，DongDong想合理使用手上的飞机折扣让自己不要吃土。给定n个城市，m条飞机航线，k次半价机会，1为DongDong家，n为萨摩耶家，每条单向边都有起点终点和机票价格（保证所有价格大于0），她可以k次使用半价折扣，求从1到n的最小花费。（若无法从1到n，输出-1）

输入描述:

第一行三个整数，n,m,k接下来m行每行,u,v,w,表示存在u到v的边，代价为w（保证所有w均为偶数）n=10000,m=50000,k=10,0=w=1000000（w为偶数），数据可能有重边和自环

输出描述:

第一行输出最小花费