伟大的中华人民共和国迎来了她的第 72 个生日！

建国以来，中国取得了举世瞩目的成就，科技发展自然也是取得了许多突破。其中，高铁毋庸置疑成为了当代中国一张熠熠生辉的名片。

适逢国庆假期，我们就来研究一下中国高铁。

在中国的某个地区，有 n 个城市，m 条双向火车铁路。城市编号为 1 ~ n，第 i 条道路连接了 u_i,v_i 两个城市，且火车通过这条火车铁路的时间为 w_i。

现在，国家决定在这一地区修建高铁。经研究，政府决定将至多 k 条火车铁路改建为高铁铁路。这样，通过这条铁路的时间便可以减少一半。也就是说，当通过某条铁路时，我们可以选择将这条 铁路改建为高铁铁路，从而使通过时间变为原先的 \frac{1}{2}。

需要注意的是：

• 一条火车铁路只能改建一次，也就是说时间减少一半的效果对一条铁路最多生效一次。
• 你不必改建完 k 条高铁铁路，也就是说改建 k-1 条，k-2 条甚至 0 条都是可以的。

根据以上条件，你需要求出在改建不超过 k 条高铁铁路的情形下，从城市 1 到城市 n 最少需要多长时间。

共 m+1 行。

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

接下来 m 行，第 i 行（总第 i+1 行）有三个整数。分别为 u_i,v_i,w_i。

一行一个整数 ans，表示从城市 1 到城市 n 的最小时间。

对于 10\% 的数据，k=0。

对于 50\% 的数据，m \leq 100。

对于 70\% 的数据，m \leq 500。

对于 100\% 的数据，1 \leq n \leq 50,1 \leq m \leq 1500,1 \leq k \leq 50；保证答案为整数，所有 w_i 为偶数；无向图保证连通、无环、无重边。