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
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    V, E = map(int, input().split())
    edges = [[INF] * V for _ in range(V)]

    for _ in range(E):
        s, t, d = map(int, input().split())
        edges[s][t] = d

    dp = [[INF] * (V + 1) for _ in range(2 ** V + 1)]
    dp[0][0] = 0
    for i in range(2 ** V):
        for j in range(V):
            for k in range(V):
                if (i >> k) & 1 == 0:
                    dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + edges[j][k])
    print(dp[2 ** V - 1][0] if dp[2 ** V - 1][0] != INF else -1)


if __name__ == "__main__":
    solve()
