짝수 번 통행료

파트리시아는 뛰어난 소프트웨어 개발자다. 그런데 이상한 습관이 하나 있다. 무엇을 하든 개수를 짝수로 맞춘다. 하루에 식사를 짝수 번 하고, 아침에는 커피 두 잔에 토스트 두 장, 치즈 두 조각을 먹는다. 영화를 보러 가면 표를 두 장 사고(다행히 같이 갈 친구가 늘 있다), 샤워는 하루에 두 번 한다. 네 번이나 여섯 번일 때도 있다.

이 습관이 걸림돌이 될 때도 있다. 파트리시아와 자동차로 함께 여행하고 싶어하는 사람은 없다. 가는 길에 통행료를 내야 한다면 통행료를 내는 횟수도 짝수여야 하기 때문이다.

파트리시아가 사는 나라의 도로는 모두 양방향이고, 도로마다 요금소가 정확히 하나 있다. 파트리시아는 다른 도시에 있는 고객을 만나러 가야 한다. 도로를 지날 때마다 그 도로의 통행료를 내며, 같은 도로를 여러 번 지날 수 있고 지날 때마다 다시 낸다. 통행료를 낸 횟수가 짝수가 되도록 자기 도시에서 고객의 도시까지 갈 때, 내야 하는 통행료 총액의 최솟값을 구하라.

첫째 줄에 도시의 수 $C$와 도로의 수 $V$가 주어진다 ($2 \le C \le 10^4$, $0 \le V \le 50000$). 도시는 1번부터 $C$번까지 번호가 붙어 있다. 이어지는 $V$개의 줄에는 각각 세 정수 $C_1$, $C_2$, $G$가 주어진다. 도시 $C_1$과 도시 $C_2$를 잇는 도로의 통행료가 $G$라는 뜻이다 ($1 \le C_1, C_2 \le C$, $1 \le G \le 10^4$). 각 도로는 서로 다른 두 도시를 잇고, 한 쌍의 도시를 직접 잇는 도로는 많아도 하나다. 파트리시아는 1번 도시에 있고 고객은 $C$번 도시에 있다.

통행료를 짝수 번 내면서 1번 도시에서 $C$번 도시까지 갈 때 필요한 통행료 총액의 최솟값을 한 줄에 출력한다. 그렇게 갈 수 없으면 $-1$을 출력한다.