시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1024 MB 198 18 11 28.947%

문제

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

예제 입력 1

10 10
1 2 2
2 3 2
3 4 2
4 5 2
5 6 2
6 7 2
7 10 2
3 8 1
8 9 5
9 6 1

예제 출력 1

14

예제 입력 2

8 8
1 2 1
2 3 1
3 4 1
4 8 1
1 5 1
5 6 1
6 7 1
7 8 1

예제 출력 2

-1

출처

Contest > 전시관 > 제1 전시관 3번

채점

  • 예제는 채점하지 않는다.