4339 - BJOI2015 回家的路

小强和阿米巴是好朋友。连接北京和小强的家乡的是错综复杂的铁路网。一共有N个站点，站点之间有长短不一的 双向的铁路。小强每次回家的时候，会从所有的最短路中随机选择一条。阿米巴门前有一条铁路。他想在不改变北 京到小强的家乡的最短路的距离的前提下，给这个铁路网再添一条长度为K的单向 单向铁路，使得小强路过阿米巴 家门口的那条铁路的概率最大。请输出这个最大概率。

第一行是三个正整数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.

输出一行两个正整数A,B，表示从A向B修建一条单向铁路。你的修建方案得出的小强路过的概率和标准答案之间的 差距不超过10-6即可算对。

尚无Spj，请谨慎提交!