This page is still under construction.

Parts of this page are still being built. What you see may change.

Ignition

Time limit1sMemory limit64 MB

Summary
Given a connected undirected weighted graph, choose a vertex to light so that the fire spreading along edges burns every point in the shortest total time.
Level

Hard8 of 10

Topics
Graph, Shortest path, Brute force, Math
Solved
No attempts yet

Problem

Seohun did badly on today's algorithms final and is in a foul mood. To work some of it off, he decides to set fire to the graph that appeared on the exam.

Seohun can light one vertex of the graph (the circles in the picture above). The moment a vertex catches fire, the fire spreads at once along every edge attached to that vertex. On an edge the fire advances 1 unit of distance per second. When fire enters one edge from both ends, the two flames burn toward each other and die out at the point where they meet.

The time to burn the graph is the time at which the last point of the graph burns. Pick the vertex to light so that this time is as small as possible. Ignore the places where edges cross in the picture above.

Input

The first line contains the number of vertices NN and the number of edges MM. (2≤N≤2002 \le N \le 200, N−1≤M≤20000N-1 \le M \le 20000)

Each of the next MM lines contains the two endpoints SS and EE of an edge and its length LL. (1≤S,E≤N1 \le S, E \le N, 1≤L≤1001 \le L \le 100)

An edge may have both endpoints at the same vertex, and two vertices may be joined by more than one edge. Every vertex can be reached from every other vertex along the edges.

Output

Print the minimum time needed to burn the whole graph, with one digit after the decimal point. The answer is always a multiple of 0.50.5, so no rounding error can appear and your output must match the answer exactly.

Hint

In the second example, lighting vertex 3 burns the graph fastest.

Examples2

  1. Example 1

    Input
    5 8
1 2 4
1 2 6
1 5 6
2 4 4
4 5 4
3 4 6
3 4 6
3 3 4
    Expected output
    9.0

  2. Example 2

    Input
    5 10
1 2 1
2 3 1
3 4 1
4 5 1
1 3 10
2 4 10
3 5 10
1 4 7
2 5 7
1 5 9
    Expected output
    6.5