The Longest Travel Route

Plenty of well known algorithms find the shortest route from one place to another. The GPS units in cars and phones tell you the fastest way to reach your destination. On vacation, though, Troy likes to travel slowly. He wants to see many new and interesting places on the way, so he takes the longest route to his destination.

A route is a sequence of distinct cities $c_1, c_2, \dots, c_k$ such that for every $1 \le i < k$ there is a road from $c_i$ to $c_{i+1}$. Troy never visits the same city twice.

Find the length of the longest route.

The first line contains the number of cities $n$ and the number of roads connecting them $m$ ($2 \le n \le 18$, $1 \le m \le n^2 - n$). There is at most one road from any given city to any other given city. Cities are numbered from $0$ to $n-1$, where $0$ is the city Troy starts in and $n-1$ is his destination.

Each of the next $m$ lines contains three integers $s$, $d$, $l$, meaning that there is a road of length $l$ km from city $s$ to city $d$ ($0 \le s \le n-1$, $0 \le d \le n-1$, $s \ne d$, $1 \le l \le 10000$). Every road is one way, so it can be taken from $s$ to $d$ only, not in the opposite direction.

There is always at least one route from city $0$ to city $n-1$.

Print a single integer, the length of the longest route that starts in city $0$, ends in city $n-1$, and visits no city twice. The length of a route is the sum of the lengths of the roads it takes.