카풀

친구들이 막 컴퓨터공학 과제를 끝냈다. 날씨가 좋아서 다 같이 Joe의 집으로 바비큐 파티를 하러 가기로 했다. 오랜 시간 코딩을 한 탓에 걸어가기엔 너무 지쳤지만, 다행히 이들이 가진 자동차만으로도 모두를 태우고 갈 수 있다.

가는 길에 각자 잠깐 들러야 할 볼일이 하나씩 있다. Joe는 버거와 음료를 사러 마트에, Jenn은 프리스비를 챙기러 집에, Jim은 피자를 사러, Jerry는 선글라스를 가지러 자기 집에 들러야 한다. 이처럼 모든 사람은 정확히 하나의 볼일을 봐야 한다.

친구들은 되도록 빨리 Joe의 집에 도착하고 싶어서, 누가 어느 차에 탈지를 정해야 한다. 모두가 도착하는 데 걸리는 시간을 최소로 만드는 사람-자동차 배정을 구하라.

도시는 주요 지점들을 잇는 도로들로 주어진다. 볼일을 보러 들러야 하는 지점들은 $1$번부터 $n$번까지 번호가 매겨져 있고, 모두가 출발하는 캠퍼스는 $0$번, Joe의 집은 $n+1$번이다. 모든 자동차는 시속 $60$km, 즉 1분에 1km를 달리므로 어떤 경로든 주행 시간(분)은 그 길이(km)와 같다. 자동차는 어떤 지점이든 멈추지 않고 지나갈 수 있으며, 자기 차에 탄 사람들의 볼일 지점에서만 멈춘다. 한 번 멈출 때마다 $5$분이 걸린다.

각 자동차는 캠퍼스에서 출발하여 (가장 좋은 순서로) 탑승자들의 볼일 지점을 모두 들른 뒤 Joe의 집에서 끝난다. 그 자동차의 이동 시간은 총 주행 시간에 탑승자 한 명당 $5$분을 더한 값이다. 환경을 생각해 친구들은 필요한 최소한의 자동차만 사용하며, 자동차 한 대에는 최대 $5$명까지 탈 수 있다.

전체 이동 시간은 각 자동차의 이동 시간 중 최댓값이다. 최적의 배정이란 이 전체 이동 시간을 가장 작게 만드는 배정이다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 15$, $1 \le m \le 1000$). 각각 무리에 속한 사람 수와 도시의 도로 수이다.

이어지는 $m$개의 줄에는 각각 하나의 도로가 세 정수 $a$, $b$, $\ell$로 주어진다. $0 \le a, b \le n+1$은 그 도로가 잇는 두 지점이고, $\ell$은 도로의 길이(km)이다. 모든 도로는 양방향으로 통행할 수 있으며, 같은 두 지점을 잇는 도로가 여러 개일 수도 있다. 도로들은 모든 지점을 서로 연결하므로 그래프는 연결되어 있다.

정수 하나를 출력한다. 자동차를 최소 개수만 쓰고 각 자동차에 최대 $5$명까지 태우는 모든 배정 중에서, 자동차 이동 시간의 최댓값이 가장 작아지도록 했을 때의 그 최솟값(분)이다.