姜维跟着诸葛亮学习一段时间后，掌握了缩地成寸的功法，但是他一天只会用两次，每次能够从u到v的路程缩短成原来的一半，魏国军队打过来了，蜀军要抢在魏军前把粮草收集到位，请问姜维该如何使用，才能让蜀军尽快收集粮草，及早做好防御。

蜀军需要从1号点出发，到达N点进行防御，姜维需要做的是，尽快的赶到N城，因为魏军一到N城就会发动进攻，但是一旦姜维到达N城，魏军就会转而攻打马谡镇守的街亭。

姜维会怎么使用这两次缩地成寸的功法，请你帮他算出他从蜀军营地出发到N城需要的时间！

第一行两个数字n和m，分别表示从营地到N城可以经过的据点数量为n,m表示据点之间的通道有m条；

接下来m行，每行3个数字u,v,w，分别表示从u到v的距离是w，它是可以双向走的。

一个数字K，表示姜维通过两次缩地成寸后，赶到N城的最短时间

数据说明：

30\%的数据：1\leq n \leq 100,1\leq m \leq 500,

60\%的数据：1\leq n \leq 500,1\leq m \leq 10000,

100\%的数据：1\leq n \leq 5000,1\leq m \leq 100000,