Yeongil Land

Yeongil Land is a theme park made up of one main gate and $N$ rides, each with an identification number. The gate is numbered 0, and the rides are numbered 1 through $N$. Directed edges connect the gate and rides, or one ride and another. Two places may be joined by several edges, and an edge may start and end at the same place.

Jeongmin visits Yeongil Land, starts at the gate, and wants to know the longest time of a route that rides every ride exactly once and returns to the gate. The rides are so fascinating that Jeongmin cannot pass one without riding it, so each ride can be reached at most once. Also, the gate cannot be visited until every ride has been ridden, and ride time is ignored.

Find the longest time for the curious Jeongmin.

The first line contains the number of rides $N$. ($1 \leq N \leq 9$)

The second line contains the number of edges $M$. ($0 \leq M \leq 10\,000$)

Each of the next $M$ lines contains $u_i$, $v_i$, and $d_i$, separated by spaces. This is an edge from the gate or ride $u_i$ to the gate or ride $v_i$, and it takes $d_i$ to travel. The sum of all travel times is less than $2^{31}$. ($0 \leq u_i, v_i \leq N$; $1 \leq d_i \leq 2^{31}-1$)

Print the longest time of a route that starts at the gate, rides every ride exactly once, and returns to the gate. If no such route exists, print -1.