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 math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

INF = sys.maxsize

v, e = map(int, input().split())
g = [[INF for _ in range(v)] for _ in range(1 << v)]

for i in range(e):
    s, t, d = map(int, input().split())
    g[s][t] = d

dp = [[INF for _ in range(v)] for _ in range(1 << v)]
dp[1][0] = 0

for bit in range(1, (1 << v) ):
    for i in range(v):
        if not bit>>i&1:
            continue

        for j in range(v):
            if bit >> j&1:
                continue
            dp[bit | (1 << j)][j] = min(dp[bit | (1 << j)][j], dp[bit][i] + g[i][j])

mn = INF

for end in range(v):
    mn = min(mn, dp[(1 << v) - 1][end] + g[end][0])
if mn == INF:
    print(-1)
else:
    print(mn)

