Military Deployment

A country has two cities and N villages. Some pairs of villages or cities are connected by bidirectional roads. Each road may have a different travel time, but traversing one road takes the same time in either direction.

The country wants to deploy G soldiers for security. Soldiers cannot be placed in a village or city; they must be placed on roads. On a road, a soldier may be placed arbitrarily close to either endpoint of that road. All soldiers may be placed at one location, split across different roads, or placed several on the same road.

After the deployment, every route from one city to the other must pass at least one soldier.

Later, the army may be called to either one of the two cities. The recall time for a city is the time at which the last deployed soldier reaches that city. Choose the deployment so that the larger of the two cities' recall times is as small as possible.

Given the cities, villages, and roads, compute this minimum possible time.

The first line contains three integers N, G, and E, where 0 <= N <= 150, 0 <= G <= 353535, and 0 <= E <= 5000.

Each of the next E lines contains three integers A, B, and C describing one road. The road connects village or city A and village or city B, and it takes C time to traverse.

Villages are numbered from 0 to N - 1. The two cities are represented by 95050 and 104729. Each C is an integer from 1 to 1000.

Among all deployments satisfying the condition, minimize the maximum of the recall times from the two cities. Print that minimum rounded to one digit after the decimal point.

If no deployment can satisfy the condition, print Impossible.