Giải bài trực tuyến

After they divided the country into counties the monkeys have a new problem: they have to stop the banana traffic. Monkey Land has N cities numbered from 1 to N connected by M two-directional roads. Between each two cities there is at most one road but between any to cities there is at least one connecting path (made up of one ore more roads). Cities 1 and N are capitals.

Lately, the banana traffic between the two capitals has increased. In order to fight the traffic the president has G soldiers he can place anywhere on a road, no matter how close to a city, but not inside a city. In case of an attack on one of the capitals all soldiers must get to that capital. Soldiers move at the same constant speed. The amount of time required for such a mobilization is equal to the maximum distances from the soldiers to one of the capitals.

Task

Write a program that finds a soldier placement solution so that any path from one capital to the other go through at least one road with a soldier and the mobilization time for the worst case scenario be minimal.

Input

The input contains on the first line three integers N M G separated by blanks.

Each of the following M lines contains three integers separated by blanks a b c meaning "there is a two-way road between city a and b of length c".

Output

The output will contain a single line with the minimum time needed for all the soldiers to get to a capital, written with one exact decimal. If there is no solution, the first line will contain -1.

Constraints

• 2 < N < 155
• 2 < M < 5055
• 0 < the length of any road < 1024
• 2 < G < 4096

Example

Input
6 6 2
1 2 1
2 3 2
3 6 1
1 4 1
4 5 3
5 6 1

Output
2.5