NKTRAFIC - Monkey island

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

Added by:Jimmy
Date:2008-01-06
Time limit:0.108s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:Campion 2005

hide comments
2012-08-13 14:05:04 Siarhei Kulik
if 2<G then then the example input violates the constraints ..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.