Description

Xiaoqiang and Amoeba are good friends. Connecting Beijing and Xiaoqiang's hometown is a complicated railway network. There are $~N~$ stations in total, and between stations there are undirected railways of different lengths. Each time Xiaoqiang goes home, he randomly chooses one path among all shortest paths.

There is a railway in front of Amoeba's house. Without changing the shortest-path distance from Beijing to Xiaoqiang's hometown, Amoeba wants to add one directed railway of length $~K~$ to the network, so that the probability that Xiaoqiang passes through the railway in front of Amoeba's house is as large as possible. Please output this maximum probability.

Constraints

$~3\leq N\leq 100000,M\leq 400000,1\leq s,K≤10000~$. It is guaranteed that no matter how you add the edge, the number of shortest paths between any two nodes in the graph will not exceed $2^{16000}~$.

Input Format

The first line contains three positive integers $~N,M~$ and $~K~$, representing the number of stations, the number of railways, and the length of the new railway. Stations are numbered from $~1~$ to $~N~$. Beijing is node $~1~$, and Xiaoqiang's hometown is node $~N~$.

The next $~M~$ lines each contain three positive integers $~u,v,s~$, indicating an undirected railway connecting stations $~u~$ and $~v~$ with length $~s~$.

The first of these $~M~$ lines describes the railway in front of Amoeba's house. There may be multiple railways between the same pair of nodes. It is also possible that $~u=v~$, i.e., a self-loop. The new railway you build may overlap an existing railway, and it may also be a self-loop. Nodes $~1~$ and $~N~$ are guaranteed to be connected.

Output Format

Output one line with two positive integers $~A,B~$, meaning that you build a directed railway from $~A~$ to $~B~$. Your construction is accepted if the difference between the probability that Xiaoqiang passes through the target railway under your plan and the standard answer is at most $10^{-6}$.

// Note: This problem lacks an $spj$, so please submit with caution.

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

2 3

Hint

After adding an edge, there are $~3~$ shortest paths in total. The probability that Xiaoqiang passes in front of Amoeba's house changes from $~1/2~$ to $~2/3~$.

Translated by ChatGPT 5