Description
To conclude on TN's life as a short-lived king, I would like to mention the collapse of his regime.
Frankly speaking, TN was an inexperienced king, which was partly proved by his failed assassination of Dzx and well demonstrated by the defeat in his battle against Ikki's invasion which led to his capture and decapitation.
According to studies of some historians, ever since he established his reign, TN had paid little attention to the fact that resource storage of the kingdom was imbalanced. Some crucial resources, including ammunition, were concentrated in a western bordering city. When he noticed that, it was all too late. The army of Ikki's kingdom had already launched invasion from the east. Now TN's most important city on the eastern border was under siege.
Had TN had the expressways in the kingdom well built it would have been enough time to transport everything in need from the west to the east. But sentences like “had it been” won't describe history. Poor traffic conditions prevented the city from avoiding falling into Ikki's hands.
Historians want to know the exact situation TN faced. Yet due to lack of records in written history this is impossible. However, they are able to find out the complete expressway system (there were more expressways built following those first ones) of TN's kingdom where as mentioned before, expressways were straight and didn't cross each other due to technical limitations. Traffic on an expressway could go in either direction. But the total amount of traffic was limited. The historians rate by estimation the capacity of each expressway in real numbers where greater figure denotes greater capacity. They want to know the maximum transport rate from the western city and the eastern city.
Input
The input consists of a single test case. The first line of input contains two positive integers N not exceeding 105 and M which are the numbers of cities and expressways. The follow N + M lines. The first N lines give the coordinates of the cities in the same way as in TN's Kingdom II - Construction assuming the positive direction of the x-axis points east and that of the y-axis points north. Among them are two cities which are uniquely the farthest to the west and to the east. They were the two bordering cities. The last M lines give the details of the expressway system. Each line contains two integers i, j and a real number c, meaning there was an expressway of estimated capacity c connecting the cities that appear in the (i + 1)-th and (j + 1)-th lines of the input.
Output
Your solution should output a single line containing the desired maximum transport rate rounded to four decimal places.
Sample Input
2 1
0 0
1 0
0 1 1
Sample Output
1.0000
http://poj.org/problem?id=2822
