로봇과 송유관 시스템

어느 나라에 거대한 송유관 시스템이 있다. 이 시스템은 관제소로 이루어져 있고, 일부 관제소 쌍은 파이프로 이어져 있다.

시스템은 연결되어 있어서 어떤 관제소에서 다른 어떤 관제소로도 파이프를 따라가는 경로가 있다. 그런데 파이프 중에는 끊어지는 순간 시스템이 더 이상 연결되지 않게 되는 것이 있다. 이런 파이프를 주요 파이프라고 부른다. 주요 파이프는 적어도 하나 있다.

회사는 주요 파이프를 정비할 로봇 두 대를 샀다. 명령을 받으면 주요 파이프 하나가 정해지고, 두 로봇은 그 파이프의 서로 다른 끝으로 각각 출발한다. 도착 시간은 목적지에 더 늦게 닿는 로봇이 걸린 시간이다.

로봇은 파이프를 따라 움직이며, 길이 1을 지나는 데 시간 1이 걸린다. 명령을 받는 순간 두 로봇은 주어진 관제소에 있다. 두 관제소는 같을 수도 있고 다를 수도 있다.

도착 시간이 가장 짧아지는 주요 파이프를 정하는 프로그램을 작성하시오.

첫째 줄에 관제소의 수 $N$과 파이프의 수 $M$이 주어진다. ($2 \le N \le 100000$, $2 \le M \le 100000$)

다음 $M$개 줄에는 각각 정수 세 개가 주어진다. 파이프가 잇는 두 관제소의 번호와 그 파이프의 길이이다. 관제소 번호는 $1$부터 $N$까지이고, 길이는 $1$ 이상 $1000$ 이하이다. 같은 두 관제소를 잇는 파이프가 여러 개 있을 수 있고, 자기 자신을 잇는 파이프는 없다.

마지막 줄에는 명령을 받는 순간 두 로봇이 있는 관제소의 번호 두 개가 주어진다.

시스템은 연결되어 있고, 주요 파이프가 적어도 하나 있다.

로봇들의 도착 시간 중 가능한 가장 짧은 값을 한 줄에 출력한다.