끝없는 악취의 늪

당신은 미로의 중심에 도달하려고 한다. 그러려면 끝없는 악취의 늪을 건너야 한다. 전설에 따르면 늪에 발가락 하나라도 담그는 순간 영원히 고약한 냄새를 풍기게 된다. 당연히 늪을 건널 때 악취를 가능한 한 적게 얻고 싶을 것이다.

다행히 악취는 결국 사라진다는 사실을 미리 알아냈다. 늪의 일부 지역은 다른 곳보다 악취를 더 많이 옮긴다. 악취를 전혀 바꾸지 않고 쉴 수 있는 작은 섬들도 있다. 첫 번째 섬은 늪 여행을 시작하는 곳이고, 마지막 섬은 반대편의 도착지다.

각 섬에서 설치된 다리를 건너 다른 섬으로 이동할 수 있다. 다리는 한 방향으로만 건널 수 있다. 여기는 끝없는 악취의 늪이므로 대부분의 다리는 악취를 일정량 늘린다. 하지만 몇몇 다리는 쾌적해서 건너면 악취가 줄어든다. 악취 수치는 0 아래로 내려갈 수 없다. 0보다 작아지게 만드는 다리를 건너면 악취는 0이 된다.

모든 섬과 다리를 지도로 정리했고, 각 다리가 악취를 얼마나 늘리거나 줄이는지도 측정했다. 그 결과 늪을 건너서 악취가 전혀 없는 상태로 나오는 것이 가능할 수도 있다!

가장 중요한 목표는 도착 섬에 최소 악취로 도달하는 것이다. 같은 섬을 여러 번 거치는 우회 경로라도 이 목표를 이룰 수 있다면 그 경로를 택해도 된다. 경로는 반드시 도착 섬에서 끝나야 한다. 다만 도착 섬에 처음 도달했다고 바로 늪을 떠날 필요는 없다. 잠시 돌아 나갔다가 나중에 같은 섬으로 돌아오는 편이 최종 악취를 줄인다면 그렇게 해도 된다.

첫 줄에는 두 정수 $n$과 $m$이 주어진다 ($1 \leq n, m \leq 2\,000$). $n$은 섬의 개수이고 $m$은 직접 연결된 다리의 개수이다.

다음 $m$개 줄에는 세 정수 $u$, $v$, $s$가 주어진다 ($1 \leq u, v \leq n$, $-10^9 \leq s \leq 10^9$). 이는 섬 $u$에서 섬 $v$로 가는 다리가 있고, 그 다리를 건너면 전체 악취가 $s$만큼 변한다는 뜻이다. 항상 $u \neq v$이며, $u$에서 $v$로 가는 다리는 최대 하나다. 반대 방향 다리는 따로 있을 수 있다.

늪을 떠날 때 가질 수 있는 최소 악취 수치를 정수 하나로 출력한다. 시작할 때 악취는 $0$이다.