점화

서훈이는 오늘 본 알고리즘 기말고사를 망쳐서 기분이 좋지 않다. 스트레스도 풀 겸, 시험에 나온 그래프를 불로 태우기로 했다.

서훈이는 그래프의 정점(위 그림에서 동그라미로 그린 곳) 중 한 곳에 불을 붙일 수 있다. 정점에 불이 붙으면 그 정점에 이어진 모든 간선을 따라 불이 곧바로 번진다. 간선 위에서 불은 1초에 1만큼의 거리를 나아간다. 한 간선에 양쪽 끝에서 불이 들어오면 두 불은 서로를 향해 태워 나가다가 만나는 지점에서 꺼진다.

그래프를 다 태우는 데 걸리는 시간은 그래프 위의 마지막 지점이 탈 때까지의 시간이다. 불을 붙일 정점을 잘 골라 이 시간을 가장 짧게 만들어라. 위 그림에서 간선끼리 교차하는 부분은 무시한다.

첫째 줄에 그래프의 정점 수 $N$과 간선 수 $M$이 주어진다. ($2 \le N \le 200$, $N-1 \le M \le 20000$)

둘째 줄부터 $M$개 줄에 각 간선의 양 끝 정점 $S$와 $E$, 그리고 길이 $L$이 주어진다. ($1 \le S, E \le N$, $1 \le L \le 100$)

양 끝이 같은 정점인 간선이 있을 수 있고, 같은 두 정점을 잇는 간선이 여러 개일 수도 있다. 모든 정점은 간선을 따라 서로 오갈 수 있다.

그래프를 모두 태우는 데 걸리는 최소 시간을 소수점 아래 한 자리까지 출력한다. 답은 항상 $0.5$의 배수여서 오차가 생길 일이 없으므로, 출력이 정답과 정확히 같아야 한다.

두 번째 예제에서는 3번 정점에 불을 붙여야 그래프가 가장 빨리 모두 탄다.