가장 짧은 순례

순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 지상에는 총 $N$ 개의 성지가 있어 $1$에서 $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을 출력한다.