영일랜드

영일랜드는 정문 하나와 놀이기구 $N$개로 이루어진 테마파크다. 정문은 0번, 놀이기구는 1번부터 $N$번까지 식별 번호로 구분된다. 정문과 놀이기구, 또는 놀이기구와 놀이기구 사이는 단방향 간선으로 이어진다. 두 장소를 잇는 간선은 여러 개일 수 있으며, 출발 장소와 도착 장소가 같을 수도 있다.

영일랜드에 놀러 간 정민이는 정문에서 출발해 모든 놀이기구를 한 번씩만 탑승하고 정문으로 돌아오는 경로 중 최장 시간을 알고 싶어 한다. 영일랜드의 놀이기구는 매혹적이어서 타지 않고 지나갈 수 없다. 따라서 각 놀이기구에는 최대 한 번씩만 도달할 수 있다. 또한 모든 놀이기구를 탑승하기 전까지는 정문을 경유할 수 없으며, 놀이기구 탑승 시간은 무시한다.

호기심이 많은 정민이를 위해 최장 시간을 구하자.

첫 번째 줄에 놀이기구의 개수 $N$이 주어진다. ($1 \leq N \leq 9$)

두 번째 줄에 간선의 개수 $M$이 주어진다. ($0 \leq M \leq 10\,000$)

다음 $M$개의 줄에는 $u_i$, $v_i$, $d_i$가 공백으로 구분되어 주어진다. 이는 정문 또는 놀이기구 $u_i$에서 $v_i$로 향하는 간선이며, 이동 시간은 $d_i$이다. 간선의 이동 시간 합은 $2^{31}$보다 작다. ($0 \leq u_i, v_i \leq N$; $1 \leq d_i \leq 2^{31}-1$)

정문에서 출발해 모든 놀이기구를 한 번씩 탑승하고 정문으로 돌아오는 경로의 최장 시간을 출력한다. 그런 경로가 없으면 -1을 출력한다.