Maximizing the Railway Passage Probability

Xiaoqiang and Amoeba are good friends. There is a complex railway network connecting Beijing (station 1) and Xiaoqiang's hometown (station N). There are N stations and M bidirectional railways with various lengths. Every time Xiaoqiang goes home he randomly chooses one of the shortest paths from Beijing to his hometown.

Amoeba has a railway passing in front of his house. He plans to add a new directed railway of length K into the network. The additional railway must not change the shortest distance from Beijing to Xiaoqiang's hometown. In other words, if d is the original shortest distance, then for the added directed edge from a station u to a station v with length K, it must satisfy \[ d_1(u) + K + d_N(v) = d, \] where \(d_1(u)\) is the shortest distance from station 1 to u and \(d_N(v)\) is the shortest distance from station v to station N. If this condition is met, the number of shortest paths that go through the new railway equals \[ \text{paths}_{uv} = (\text{# of shortest paths from 1 to } u) \times (\text{# of shortest paths from } v \text{ to } N). \] Your task is to choose the endpoints u and v for the new railway so that the probability that Xiaoqiang’s randomly chosen shortest path uses this special railway, \[ P = \frac{\text{paths}_{uv}}{\text{total number of shortest paths from 1 to } N}, \] is maximized. Print this maximum probability. If no valid directed railway can be added, print 0.

inputFormat

The first line contains three integers N, M and K (2 ≤ N ≤ 10^5 is assumed for practical limits, M is the number of bidirectional railways, and K is the length of the new directed railway).

The next M lines each contain three integers u, v and w representing a bidirectional railway between stations u and v with length w (\(w > 0\)).

outputFormat

Output a floating point number representing the maximum probability that Xiaoqiang’s chosen shortest path passes through Amoeba's new railway. The answer should be correct within an absolute or relative error of 1e-6.

sample

4 4 1
1 2 1
2 4 1
1 3 1
3 4 1

0.5