페리

펭귄 강은 남극에 있는 섬 $N$개로 이루어진 지역에 산다. 섬에는 $1$번부터 $N$번까지 번호가 붙어 있고, 강의 집은 $1$번 섬에 있다. 오늘 강은 감기에 걸려서 $N$번 섬에서 일하는 수의사를 찾아가려고 한다.

평소라면 헤엄쳐 가겠지만 감기 때문에 오늘은 페리를 타고 가기로 했다. 페리는 모두 $M$대이고 $1$번부터 $M$번까지 번호가 붙어 있다. $i$번 페리는 $A_i$번 섬에서 $B_i$번 섬으로 승객을 $C_i$달러에 실어 나르고, 한 방향으로만 운항한다. 한 섬에서 다른 섬으로 가는 페리는 많아야 한 대이고, 요금이 $0$달러인 페리도 있을 수 있다. 강은 가능한 한 적은 돈으로 $N$번 섬까지 가고 싶다.

그런데 하필 오늘 선장들이 돈을 더 받아낼 궁리를 시작했다. 선장들은 강이 $1$번 섬에서 $N$번 섬까지 페리를 타고 간다는 사실을 알고, 강의 여정을 최대한 비싸게 만들기로 담합했다. 같은 섬에서 출발하는 페리의 선장끼리는 목적지를 서로 바꿀 수 있다. 다만 계약 때문에 각 페리의 요금은 목적지가 바뀌어도 그대로다. 예를 들어 $1$번, $2$번, $3$번 페리가 모두 $1$번 섬에서 출발해 각각 $2$번, $3$번, $4$번 섬으로 가고 요금이 각각 $10$달러, $20$달러, $30$달러라고 하자. 여기서 $1$번 페리와 $2$번 페리의 선장이 목적지를 맞바꾸면 $1$번 페리는 요금 $10$달러 그대로 $3$번 섬으로 가고, $2$번 페리는 요금 $20$달러 그대로 $2$번 섬으로 간다.

선장들은 강이 어떤 페리에도 타기 전에 최종 목적지를 공표하고, 공표한 다음에는 목적지를 바꾸지 못한다. 강은 선장들의 속셈을 알지만 집을 나서기 전에는 페리의 목적지를 모른다. 수의사에게 도착하는 데 확실히 충분한 최소 금액을 구하시오. 즉, 선장들이 강의 최소 비용 경로를 최대한 비싸게 만들 때 강이 $N$번 섬에 도착하는 데 드는 최소 비용을 구하면 된다.

프로그램은 표준 입력에서 읽는다. 첫째 줄에 정수 $N$과 $M$이 주어진다. 다음 $M$개 줄에는 각각 정수 $A_i$, $B_i$, $C_i$가 주어지며, 페리 한 대를 나타낸다. $1$번 섬에서 $N$번 섬으로 가는 경로는 항상 존재한다.

표준 출력에 정수 하나를 출력한다. 강이 수의사에게 도착하는 데 필요한 최소 금액을 달러 단위로 출력한다.