There and Back Again

도시는 $1$번부터 $n$번까지 번호가 붙은 $n$개가 있습니다. 2024 ICPC Asia Pacific Championship 대회는 도시 $n$번인 하노이에서 열립니다.

도로는 $1$번부터 $m$번까지 번호가 붙은 $m$개의 양방향 도로가 있습니다. 도로 $i$는 도시 $u_i$와 $v_i$를 잇고, 어느 방향으로 이동하든 $t_i$의 시간이 걸립니다. 각 도로는 서로 다른 두 도시를 잇고, 서로 다른 도로는 서로 다른 도시 쌍을 잇습니다.

당신은 도시 $1$번에 삽니다. 대회에 참가하려고 도로를 따라 도시 $n$번까지 간 뒤, 다시 도로를 따라 도시 $1$번으로 돌아오려 합니다. 같은 경로를 되풀이하면 지루하므로, 두 이동의 경로는 달라야 합니다. 두 경로가 다르다는 것은 한 경로가 지나는 서로 다른 도로의 집합이 다른 경로의 도로 집합과 다르다는 뜻입니다.

각 이동에서는 같은 도시나 같은 도로를 여러 번 지나도 됩니다. 목적지인 도시 $1$번이나 도시 $n$번에 도착한 뒤에도 계속 이동해도 됩니다. 이동 시간은 지나간 도로들의 시간을 모두 더한 값입니다. 한 도로를 여러 번 지나면 그 도로의 시간도 지난 횟수만큼 더합니다.

위 조건을 만족하는 두 이동의 총 이동 시간의 최솟값을 구하세요. 조건을 만족할 수 없다면 그 사실을 알려주세요.

첫 줄에 두 정수 $n$과 $m$이 주어집니다 ($2 \le n \le 100\,000$; $1 \le m \le \min(\frac{n(n-1)}{2}, 300\,000)$). 이어지는 $m$개의 줄에는 각각 세 정수 $u_i$, $v_i$, $t_i$가 주어집니다 ($1 \le u_i < v_i \le n$; $1 \le t_i \le 1000$). 서로 다른 도로는 서로 다른 도시 쌍을 잇습니다.

조건을 만족하는 두 이동의 총 이동 시간의 최솟값을 정수 하나로 출력합니다. 그런 두 이동이 없으면 $-1$을 출력합니다.