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
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
G = list2d(N, N, INF)
for i in range(M):
    s, t, d = MAP()
    G[s][t] = d

# dp[bit][i] := 今iにいる時の、集合bitの最短距離
dp = list2d(1<<N, N, INF)
# 初期化：頂点0を開始位置として距離0にする
dp[1][0] = 0

for bit in range(1, (1<<N)-1):
    for i in range(N):
        # 頂点iが集合bitに含まれていない
        if not bit>>i&1: continue
        for j in range(N):
            # 頂点jは既に集合bitに含まれている
            if bit>>j&1: continue
            # 頂点iからjへの移動を遷移させる
            dp[bit+(1<<j)][j] = min(dp[bit+(1<<j)][j], dp[bit][i] + G[i][j])

mn=INF
for end in range(N):
    # 最後の頂点から戻ってくる分を足す
    mn = min(mn, dp[(1<<N)-1][end] + G[end][0])
if mn==INF:
    print(-1)
else:
    print(mn)

