도로 검문

그림 1은 어떤 도시의 주요 지점과 그 지점들을 잇는 도로의 이동 시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 뜻하고, 두 지점을 잇는 도로에 적힌 수는 그 도로를 지날 때 걸리는 시간을 분 단위로 나타낸다. 두 지점 a와 b를 잇는 도로는 도로(a, b)라고 부른다.

그림 1

예를 들어 도로(1, 2)와 도로(2, 3)를 지나 지점 1에서 지점 3으로 가면 3분이 걸린다. 모든 도로는 양방향이므로 도로(a, b)를 지나는 시간과 도로(b, a)를 지나는 시간은 항상 같다.

범죄 용의자는 입력으로 주어진 도시의 지점 1로 들어와 가능한 한 빨리 지점 N으로 빠져나가려고 한다. 경찰은 이를 알고 도로 하나를 골라 그 도로에서 검문을 한다. 용의자는 검문 중인 도로를 피하면서 가장 빠른 경로로 도시를 빠져나가려 한다. 경찰이 어떤 도로를 선택하느냐에 따라, 검문이 없을 때보다 용의자의 최단 탈출 시간이 더 길어질 수 있다.

구해야 하는 값은 도로 하나를 검문하여 만들 수 있는 최대 탈출 지연 시간이다. 조건은 다음과 같다.

1. 두 지점을 직접 연결하는 도로가 있다면 그 도로는 하나뿐이다.
2. 도시의 지점은 1번부터 N번까지의 연속된 정수로 표시된다.
3. 용의자가 도시에 들어오는 지점은 항상 1번이고, 탈출하기 위해 마지막으로 도달해야 하는 지점은 항상 N번이다.
4. 용의자는 검문 중인 도로를 피하면서 가장 빨리 탈출하려 하고, 경찰은 도로 하나를 골라 그 탈출 시간을 최대한 늦추려 한다.
5. 각 도로를 지나는 데 걸리는 시간은 항상 양의 정수이다.

도로망에 따라 경찰이 어떤 도로를 막으면 용의자가 도시를 빠져나갈 수 없을 수도 있다. 이 경우 검문으로 인한 지연 시간은 무한대이며, -1을 출력해야 한다.

그림 1에서 검문이 없을 때 용의자가 도시를 빠져나가는 데 걸리는 시간은 4분이다. 경찰이 도로(4, 3)을 막으면 탈출 시간이 늘어나지 않으므로 지연 시간은 0이다. 도로(2, 3)을 막으면 가장 빠른 탈출 시간이 5분이 되어 지연 시간은 1분이고, 도로(3, 6)을 막으면 지연 시간은 2분이다.

입력으로 주어진 도로망에서 경찰이 도로 하나를 막아 만들 수 있는 최대 지연 시간을 정수로 출력하라. 지연 효과가 없으면 0을 출력하고, 탈출을 불가능하게 만들 수 있으면 -1을 출력한다.

첫 줄에 지점의 수 N(6 <= N <= 1000)과 도로의 수 M(6 <= M <= 5000)이 주어진다. 이어지는 M개의 줄에는 도로(a, b)와 통과 시간 t가 a b t 형식으로 주어진다. 이때 a < b이고, 1 <= t <= 10000이다.

경찰이 도로 하나를 막아 지연시킬 수 있는 최대 시간을 정수로 출력한다. 단, 지연 시간이 무한대이면 -1을 출력한다.