18344번 - 가장 짧은 순례 서브태스크

문제

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

제한

서브태스크 1 (1점)

• 1ドル \le N,M \le 10^2$

서브태스크 2 (10점)

• 1ドル \le N,M \le 10^4$

서브태스크 3 (100점)

• 1ドル \le N,M \le 10^6$

힌트