众所周知，垃圾佬喜欢打Dota，而且打得非常好。今天垃圾佬和T^T进行了一场大战。现在垃圾佬拿到一张地图，地图上一共有n个地点，垃圾佬的英雄处于1号点，T^T的基地位于n号点，垃圾佬要尽快地选择较短的路线让他的英雄去虐掉T^T的基地。但是T^T早就料到了这一点，他有可能会开挂(BS~)使用一种特别的魔法，一旦垃圾佬所走的路线的总长度等于最短路的总长度时，垃圾佬的英雄就要和这种魔法纠缠不休。这时垃圾佬就不得不选择非最短的路线。现在请你替垃圾佬进行规划。
Hint:
对于本题中非最短路线的定义：不管采取任何改道、迂回方式，只要垃圾佬所走的路线总长度不等于1到n最短路的总长度时，就算做一条非最短的路线。
数据保证存在合法解。
多组测试数据（不超过10组）
第一行为n，m(表示一共有m条路径)
接下来m行，每行3个整数a，b，c，表示编号为a,b的点之间连着一条需花费时间为c的无向路径。
接下来一行有一个整数p，p=0表示T^T没有开挂使用这种魔法，p=1则表示使用了。
（1<=n<=10000, 1<=m<=50000,p=0或1，0<=c<=2^31-1）
对于每组数据，输出所花费的最短时间T，数据保证一定可以到达n。
5 5 1 2 1 1 3 2 3 5 2 2 4 3 4 5 1 0 5 5 1 2 1 1 3 2 3 5 2 2 4 3 4 5 1 1
4 5