즉시 배송

마이크와 존은 즉시 배송의 배달원입니다. 어느 날 두 사람은 도시 곳곳에 아주 많은 소포를 배달하라는 요청을 받았습니다.

두 사람이 일하는 도시의 교통망은 여러 교차로와 이 교차로들을 잇는 도로들로 이루어져 있습니다. 모든 도로는 양방향이며, 임의의 두 교차로는 (직접 또는 다른 교차로를 거쳐) 서로 오갈 수 있습니다.

마이크와 존은 모든 소포를 배달하기 위해 모든 교차로를 방문해야 합니다. 두 사람은 이 일을 둘로 나누어, 마지막 배달이 끝나는 시각을 최소화하려고 합니다.

두 배달원은 시각 0에 동시에 사무소(1번 교차로)에서 출발하며, 각자 도로를 따라 자유롭게 이동합니다(같은 도로를 여러 번 지나도 됩니다). 한 배달원의 이동 시간은 그가 지나간 도로들의 시간을 모두 더한 값이고, 마지막 배달 시각은 두 배달원의 이동 시간 중 더 큰 쪽입니다. 모든 교차로가 두 사람 중 적어도 한 명에게 방문되도록 배정하여, 이 마지막 배달 시각을 최소로 만드십시오.

첫째 줄에 교차로의 수 n과 도로의 수 m이 주어집니다 (1 ≤ n ≤ 18).

이어지는 m개의 줄에는 각 도로가 하나씩 주어집니다. 각 줄에는 도로가 잇는 두 교차로의 번호 x와 y (1 ≤ x, y ≤ n), 그리고 그 도로를 지나는 데 걸리는 시간 t (1 ≤ t ≤ 1000)가 주어집니다. 어떤 두 교차로를 잇는 도로는 최대 한 개이며, 한 교차로를 자기 자신과 잇는 도로는 없습니다.

사무소는 1번 교차로에 있습니다.

마지막 소포가 배달될 수 있는 가장 이른 시각, 곧 가능한 마지막 배달 시각의 최솟값을 정수 하나로 한 줄에 출력하십시오.