SPRING - Spring Loaded

no tags 

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).

spring example

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

hide comments
[Rampage] Blue.Mary: 2016-03-18 05:20:54

It seems that the input data contains test cases with assertion "0 <= A, B <= n-1 " failed.

Edit After AC: SPFA passed while bellman-ford failed. Strange.

Last edit: 2017-10-19 07:50:27
:D: 2012-12-05 19:55:37

Thank you VERY MUCH Bruno!! I would never figured it out. I simply thought my solution was too slow (got TLE because of this).

Bruno Adami: 2012-09-04 16:39:45

The input ends with EOF not with 0 0 0!!

:D: 2012-05-05 17:40:58

The description is missing "^" characters. The constraints should probably be:
1 <= M <= 10^4
1 <= D <= 10^5
1 <= K <= 10^5


Added by:Paulo Costa
Date:2012-01-19
Time limit:3.418s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Unicamp