第一行是三个正整数N,M和K，表示站点的数量，铁路线的数量和新开的铁路线的长度。站点从1编号到N。北京是1
号点，小强的家乡是N号。接下来M行，每行三个正整数u,v,s表示有一条连接站点u和v的铁路线长度是s。这M行中
的第一行描述的是阿米巴家门口的铁路。两个点之间可能有多条铁路。也有可能u=v，即，有自环。你新修建的铁
路也可以和已有线路重合，也可以是自环。1和N之间一定是连通的。
3≤N≤100000，M≤400000，1≤s,K≤10000,保证无论如何加边图中任两点之间的最短路的数量都不超过2^16000.