Bob have just got a new toy from his Physics teacher to play with. It is called the Super Coiled Spring Loaded String (SCSLS for short) and it involves coiled springs, but unfortunately no magnets. The complex structure of the trinket is made of N bars (numbered from 0 to N − 1) and M springs (numbered from 0 to M − 1), each of which connects two different bars. All springs are laid out longitudinally to the entire string while the bars are perpendicular to them. The bars can be positioned freely along the longitudinal axis, but when two bars connected by a spring are pulled away from each other, a restoring force appears at the spring. Bob knows that this elastic force is given by Hooke’s Law, which states that |F | = kx, where k is a spring constant, x is the displacement of the spring and |F | is the absolute value of the force. Because the SCSLS is a very strange device, its springs are also special since they are Zero-length springs, each with a specific constant ki . This kind of spring have infinitesimal length so that when it is stretched, its length is equal to its displacement. Bob wants to leave his new toy displayed in his bedroom and he will do so by nailing the bars to the wall. He needs to position them horizontally such that bars 0 and N − 1 are D units distant from each other and the remaining bars are between them (in any relative order). Being a very meticulous kid, he always takes good care of all his toys. So, he wants to achieve a configuration such that the maximum force exerted on any spring is the lowest possible (because this way the springs are supposed to have greater durability).

For example, in the figure above we have N = 4 bars and M = 4 springs showed at the left in their initial configuration. Suppose the spring constants are k0 = 10, k1 = 20, k2 = 10 and k3 = 1 and Bob wants a total distance of D = 10. The best configuration is showed at the right, in which the springs are subject to forces |F0| = 40, |F1| = 40, |F2| = 40 and |F3| = 6, all of which are no greater than 40.

Input

Each test case is described using several lines. The first line contains three integers N, M and D representing respectively the number of bars (2 ≤ N ≤ 100), the number of springs (1 ≤ M ≤ 10^4) and the needed distance between bars 0 and N − 1 (1 ≤ D ≤ 10^5). Each of the next M lines describes a spring using two distinct integers A, B and an integer K, indicating that there is a spring connecting bars A and B (0 ≤ A, B ≤ N − 1) with spring constant K (1 ≤ K ≤ 10^5). The last test case is followed by a line containing three zeros.

Output

For each test case output a line with the lowest possible value of the maximum elastic force in a valid configuration. Your answer should be rounded to two decimal digits.

Example

Input:
3 2 5
1 0 1
1 2 1
3 3 5
1 0 1
1 2 1
0 2 2
4 4 10
0 2 10
1 2 20
1 3 10
2 3 1
0 0 0

Output:
2.50
10.00
40.00