가장 긴 여행 경로

한 지점에서 다른 지점으로 가는 가장 짧은 경로를 찾는 알고리즘은 잘 알려져 있다. 자동차와 휴대전화에 달린 GPS 장치는 목적지까지 가는 가장 빠른 길을 알려 준다. 그런데 휴가를 떠난 Troy는 느리게 여행하고 싶어 한다. 가는 길에 새롭고 흥미로운 곳을 많이 구경하려고, 목적지까지 가는 가장 긴 경로를 택하려 한다.

경로는 서로 다른 도시를 나열한 수열 $c_1, c_2, \dots, c_k$ 이고, 모든 $1 \le i < k$ 에 대해 $c_i$ 에서 $c_{i+1}$ 로 가는 도로가 있어야 한다. Troy는 같은 도시를 두 번 방문하지 않는다.

가장 긴 경로의 길이를 구하라.

첫째 줄에 도시의 수 $n$과 도시를 잇는 도로의 수 $m$이 주어진다 ($2 \le n \le 18$, $1 \le m \le n^2 - n$). 어떤 도시에서 다른 어떤 도시로 가는 도로는 많아야 하나다. 도시에는 $0$부터 $n-1$까지 번호가 붙어 있고, $0$은 Troy가 출발하는 도시, $n-1$은 목적지다.

다음 $m$개의 줄에 각각 세 정수 $s$, $d$, $l$이 주어진다. 도시 $s$에서 도시 $d$로 가는 길이 $l$ km의 도로가 있다는 뜻이다 ($0 \le s \le n-1$, $0 \le d \le n-1$, $s \ne d$, $1 \le l \le 10000$). 모든 도로는 일방통행이라서 $s$에서 $d$ 방향으로만 지날 수 있고, 반대 방향으로는 지날 수 없다.

도시 $0$에서 도시 $n-1$로 가는 경로는 항상 하나 이상 있다.

도시 $0$에서 출발해 도시 $n-1$에서 끝나고 같은 도시를 두 번 방문하지 않는 가장 긴 경로의 길이를 정수 하나로 출력한다. 경로의 길이는 지나간 도로의 길이를 모두 더한 값이다.