伟大的中华人民共和国迎来了她的第 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 最少需要多长时间。