题目描述

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

输入格式

第一行是三个正整数$~N,M~$和$~K~$，表示站点的数量，铁路线的数量和新开的铁路线的长度。站点从$~1~$编号到$~N~$。北京是$~1~$号点，小强的家乡是$~N~$号。接下来$~M~$行，每行三个正整数$~u,v,s~$表示有一条连接站点$~u~$和$~v~$的铁路线长度是$~s~$。

这$~M~$行中的第一行描述的是阿米巴家门口的铁路。两个点之间可能有多条铁路。也有可能$~u=v~$，即，有自环。你新修建的铁路也可以和已有线路重合，也可以是自环。$~1~$和$~N~$之间一定是连通的。

$~3\leq N\leq 100000,M\leq 400000,1\leq s,K≤10000~$，保证无论如何加边图中任两点之间的最短路的数量都不超过$2^{16000}~$。

输出格式

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

//注意：本题因缺少$spj$，请谨慎提交。

3 3 1
1 2 1
2 3 1
1 3 2

2 3

提示

添加边之后，一共有$~3~$条最短路，小强会路过阿米巴门前的概率由$~1/2~$变为$~2/3~$.