For a given weighted directed graph G(V, E), find the distance of the shortest route that meets the following criteria:

* It is a closed cycle where it ends at the same point it starts.
* It visits each vertex exactly once.

Constraints

* 2 ≤ |V| ≤ 15
* 0 ≤ di ≤ 1,000
* There are no multiedge

Input


|V| |E|
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


|V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target vertices of i-th edge (directed) and di represents the distance between si and ti (the i-th edge).

Output

Print the shortest distance in a line. If there is no solution, print -1.

Examples

Input

4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4


Output

16


Input

3 3
0 1 1
1 2 1
0 2 1


Output

-1
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


class Edge:
    def __init__(self,arg_to,arg_dist):
        self.to = arg_to
        self.dist = arg_dist


V,E = map(int,input().split())

POW = [None]*(V+1)
POW[0] = 1
for i in range(1,V+1):
    POW[i] = POW[i-1]*2

G = [[] for _ in range(V)]

for _ in range(E):
    from_,to_,dist = map(int,input().split())
    G[from_].append(Edge(to_,dist))

#経路は輪になるので、スタートは0として良い
start = 0
dp = [[BIG_NUM]*V for _ in range(POW[V])]

dp[POW[start]][start] = 0

for state in range(1,POW[V]):
    for last_node in range(V):
        if dp[state][last_node] == BIG_NUM:
            continue
        for edge in G[last_node]:
            if state & POW[edge.to] != 0:
                continue #訪問済
            next_state = state+POW[edge.to]
            if dp[next_state][edge.to] > dp[state][last_node]+edge.dist:
                dp[next_state][edge.to] = dp[state][last_node]+edge.dist

ans = BIG_NUM
#startに戻る
for last_node in range(V):
    if dp[POW[V]-1][last_node] == BIG_NUM:
        continue
    for edge in G[last_node]:
        if edge.to != start:
            continue
        ans = min(ans,dp[POW[V]-1][last_node]+edge.dist)

if ans == BIG_NUM:
    print("-1")
else:
    print("%d"%(ans))

