페리들 Batch 컴파일 명령

최근 남극으로 이사 간 펭귄 지학이는 1부터 $N$까지의 번호가 붙어 있는 $N$개의 섬들에 살고 있습니다. 지학이의 집은 1번 섬에 있습니다. 지학이는 감기에 걸렸기 때문에, $N$번 섬에 사는 수의사를 찾아갈 계획을 세웁니다.

보통 그는 수영을 하겠지만, 지학이는 감기에 걸렸기 때문에 목적지까지 페리를 타고 가기로 합니다. $1$부터 $M$까지의 번호가 붙은 $M$개의 페리가 있고, $i$번 페리는 $A_{i}$번 섬부터 $B_{i}$번 섬으로 $C_{i}$달러를 받고 승객을 태워줍니다. (단방향) 임의의 한 섬에서부터 또다른 한 섬으로 이동하는 페리는 많아야 1개이고, 페리들은 무료 서비스를 제공할 수도 있습니다. (즉 $C_{i}=0$) 지학이는 최소한의 비용으로 $N$번 섬으로 가고자 합니다.

불운하게도, 페리 선장들은 돈을 벌기 위해 책략을 꾸몄습니다. 그들은 지학이가 페리를 이용해서 1번 섬으로부터 $N$번 섬으로 이동하려는 것을 알고 있기에, 그들은 지학이가 최대한 많은 돈을 내게 하려고 음모를 꾸몄습니다. 같은 섬에서 출발하는 페리 선장들은 그들끼리 목적지를 바꿀 수 있습니다. (순열 관계) 하지만 그들의 계약서에 따르면 각 페리는 목적지가 달라지더라도 그 가격은 그대로 유지됩니다. 예를 들어, 1번, 2번, 3번 페리가 1번 섬에서 출발해서 각각 2번, 3번, 4번 섬에 도착하며, 가격은 각각 10달러, 20달러, 30달러라고 가정해 봅시다. 1번 페리와 2번 페리의 선장은 도착지를 서로 바꿔서, 1번 페리가 3번 섬에 도착하게 하고 (가격은 여전히 10달러), 2번 페리가 2번 섬에 (가격은 여전히 20달러) 도착하도록 할 수 있습니다.

악랄한 음모를 꾸민 선장들은 지학이가 페리에 탑승하기 전에 그들의 페리가 어떤 섬으로 갈 지 발표할 것입니다. 발표 후에는 목적지를 바꿀 수 없습니다. 지학이는 선장들이 이러한 음모를 꾸민 것은 알고 있으나 집을 떠나기 전 선장들이 바꾼 페리들의 목적지를 알지는 못합니다. 지학이는 여러분에게 도움을 요청합니다. 그는 그가 페리를 타고 수의사에게 도착하기 위해 지참해야 할 최소한의 돈이 얼마인지 알고자 합니다.

입력 형식

첫 번째 줄에 $N$과 $M$이 주어집니다. 다음 연속한 $M$개 줄에 3개의 정수 $A_{i}, B_{i}, C_{i}$가 주어집니다.

출력 형식

첫 번째 줄에 지학이가 수의사에게 도착하기 위해 지참해야 할 최소한의 돈을 달러 단위로 출력합니다.

서브태스크

각 입력에 대해 실행 시간 제한은 1.0초입니다. 여러분이 제출한 코드는 아래 입력 조건에 따라 평가될 것입니다.

1. (7점) $2 \le N \le 100,000, M = 2N-4$. 1번 섬에서 출발하는 페리가 $N-2$개 있으며, 각 페리는 $2, 3, \cdots, (N-1)$번 섬에 도착합니다. 또다른 $N-2$개의 페리는 $2, 3, \cdots, (N-1)$번 섬에서 출발해서 $N$번 섬에 도착합니다.
2. (10점) $2 \le N \le 100,000, 1 \le M \le 300,000.$ 1번 섬에서 출발하는 페리가 1개 이상 있습니다. $2, 3, \cdots, N-1$번 섬에서 출발하는 페리가 각각 하나씩 있습니다.
3. (11점) $2 \le N \le 100,000, 1 \le M \le 300,000.$ 사이클이 없습니다. 다시 말해서, 지학이가 어떤 섬을 페리를 타고 떠나면, 페리를 타고 그 섬으로 돌아갈 수는 없다는 것입니다.
4. (12점) $2 \le N \le 100,000, 1 \le M \le 300,000.$

모든 $C_{i}$에 대해 $0 \le C_{i} \le 10,000.$

예제

예제 설명

1번, 3번, 5번 페리가 목적지를 서로 바꿉니다. 1번 페리는 이제 3번 섬으로(비용은 여전히 2달러), 3번 페리는 4번 섬으로 (비용은 여전히 10달러), 5번 페리는 2번 섬으로 (비용은 여전히 7달러) 이동합니다. 지학이가 지참해야 할 최소한의 돈은 9달러입니다. (1번 -> 3번 -> 4번 또는 1번 -> 2번 -> 4번) 9달러보다 많이 지불하도록 페리들의 도착지를 바꿀 방법은 존재하지 않습니다.