题目描述

光头强想要完成一次说走就走的旅行，他来到了某旅行社进行咨询。

地图可以看做是一张 $n$ 个顶点 $m$ 条边的简单无向图，每个顶点表示一座城市，在两个城市之间移动需要花费连接这两座城市的边的边权的代价。

光头强是这家旅行社的 vip 用户，他拥有 $k$ 张打折券，在一次移动时他可以使用打折券，使得这次移动的代价变成之前的一半，每条边只能使用一次打折券。

光头强现在在 1 号城市，他想知道他最少花费多少代价可以到达 $n$ 号城市，数据保证两地连通。

图用以下形式给出：

第一行输入三个整数 $n,m,k$ ，表示图的顶点数、边数和打折券的数量，顶点编号从 1 到 $n$ 。

接下来 $m$ 行，每行三个整数 $x,y,z$ ，表示 $x, y$ 之间有一条边，边权为 $z$ 。

输入格式

第一行三个整数 $n,m,k$ 。

接下来 $m$ 行，每行有三个整数，代表一条边。

输出一个数表示答案。

3 2 1
1 2 4
2 3 6

对于所有数据，保证 $2≤n≤500,1≤m≤2000,1≤k≤10,1≤x,y≤n,x≠y,1≤z≤10000$ , 保证 $z$ 是偶数。