개코전쟁

동물나라의 지도는 N개의 정점과 M개의 도로로 이루어진 양방향 가중치 그래프이다. 개미왕국은 1번 정점에 있고, 코끼리왕국은 N번 정점에 있다. 개미왕국은 항상 1번 정점에서 N번 정점까지 최단거리로 이동한다.

전쟁을 최대한 늦추기 위해 도로를 정확히 하나 파괴하려고 한다. 도로 하나가 사라진 뒤에도 개미왕국은 다시 1번 정점에서 N번 정점까지의 최단경로를 선택한다.

어떤 도로 하나를 파괴하더라도 1번 정점에서 N번 정점으로 도달할 수 있음이 보장된다. 도로 하나를 파괴했을 때, 1번 정점에서 N번 정점까지의 최단거리를 가능한 한 크게 만들고자 한다. 그 최댓값을 구하라.

첫 줄에 정점의 개수 N과 도로의 수 M이 주어진다. 1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N-1)/2 이다.

다음 M개의 줄에는 각 도로의 정보 x_i y_i z_i가 주어진다. 이는 정점 x_i와 정점 y_i를 잇는 도로가 있으며, 그 도로를 지나는 데 z_i만큼의 시간이 걸린다는 뜻이다.

같은 두 정점 사이에는 도로가 두 개 이상 존재하지 않는다. 모든 도로는 양방향이며, 도로 하나를 파괴하면 양방향 모두 사용할 수 없게 된다. 1 ≤ x_i, y_i ≤ N, 1 ≤ z_i ≤ 1000 이다.

적절한 도로 하나를 파괴했을 때 1번 정점에서 N번 정점까지의 최단거리의 최댓값을 출력한다.