가장 짧은 순례

순례자는 끝나지 않을 것처럼 보이는 순례를 계속하고 있다. 지상에는 1부터 $N$까지 번호가 붙은 $N$개의 성지가 있다. 도로는 $M$개 있으며, $i$번 도로는 $x\_i$번 성지와 $y\_i$번 성지를 $w\_i$분 만에 오갈 수 있게 한다.

순례자는 1번 성지에서 출발해 $N$번 성지에서 끝나는 새로운 순례를 계획하고 있다. 이 순례는 1번과 $N$번 성지를 포함해 정확히 여덟 개의 서로 다른 성지를 방문한다. 한 성지는 두 번 이상 방문할 수 없다.

도로에서 이동하는 시간만 고려할 때, 순례에 걸리는 가장 짧은 시간을 구하시오.

첫 번째 줄에 성지의 개수 $N$과 도로의 개수 $M$이 주어진다.

다음 $M$개의 줄 중 $i$번째 줄에는 $i$번 도로의 정보 $x\_i, y\_i, w\_i$ ($1 \leq x\_i,y\_i \leq N$, $x\_i \neq y\_i$, $1 \leq w\_i \leq 10^8$)가 주어진다. 같은 두 성지를 잇는 도로는 한 번만 주어진다.

첫 번째 줄에 순례에 걸리는 가장 짧은 시간을 분 단위로 출력한다. 조건을 만족하는 순례가 없으면 -1을 출력한다.