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
using System;
using System.Collections.Generic;
using System.Linq;

class PriorityQueue<T> where T : IComparable<T> {
    private List<T> _buf = new List<T>();
    private IComparer<T> _comp;

    private void Swap(int a, int b) {
        T t = _buf[a];
        _buf[a] = _buf[b];
        _buf[b] = t;
    }

    private int Compare(T a, T b) {
        if (_comp == null) return a.CompareTo(b);
        return _comp.Compare(a, b);
    }

    public int Count { get { return _buf.Count; } }

    public PriorityQueue() {
    }

    public PriorityQueue(IComparer<T> comp) {
        _comp = comp;
    }

    public void Enqueue(T x) {
        _buf.Add(x);

        // shiftup
        int p = Count-1;
        while (p > 0) {
            int parent = (p - 1) / 2;
            if (Compare(_buf[parent], _buf[p]) <= 0)
                break;
            Swap(parent, p);
            p = parent;
        }
    }

    public T Dequeue() {
        if (Count == 0)
            throw new IndexOutOfRangeException();

        T ret = _buf[0];
        _buf[0] = _buf[Count-1];
        _buf.RemoveAt(Count-1);

        // shiftdown
        int p = 0;
        while (p < Count) {
            int c = p * 2 + 1; // ?????????
            if (c >= Count) break;

            if (c+1 < Count) { // c+1 ????????????
                if (Compare(_buf[c+1], _buf[c]) < 0) { // ??????????????????????°???????
                    c++;
                }
            }

            if (Compare(_buf[p], _buf[c]) <= 0)
                break;
            Swap(p, c);
            p = c;
        }

        return ret;
    }
}

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    struct D : IComparable<D> {
        public int node;
        public int visited;
        public int cost;
        public bool finished; // ??¨??????note????¨??????????

        public int CompareTo(D o) { return cost - o.cost; }
    }

    static int Calc_1(int start, int v, int[,] adj) {
        var q = new PriorityQueue<D>();
        q.Enqueue(new D { node = start, visited = (1 << start), cost = 0, finished = false });

        var memo = new int[v, (1 << v)];
        for (int i = 0; i < v; i++)
            for (int j = 0; j < (1 << v); j++)
                memo[i, j] = int.MaxValue;

        while (q.Count > 0) {
            D d = q.Dequeue();

            if (d.finished) return d.cost;

            if (d.visited == (1 << v)-1) {
                // ??¨???????????????????¨???????????????§???start ?????????
                if (adj[d.node, start] != -1) {
                    int cost = d.cost + adj[d.node, start];
                    q.Enqueue(new D { node = start, visited = d.visited, cost = cost, finished = true });
                }
                continue;
            }

            if (memo[d.node, d.visited] < d.cost) continue;
            memo[d.node, d.visited] = d.cost;

            for (int i = 0; i < v; i++) {
                if (adj[d.node, i] == -1) continue; // ????????????

                if ((d.visited & (1 << i)) > 0) continue; // ?¨??????????

                int vv = d.visited | (1 << i);
                int cost = d.cost + adj[d.node, i];
                q.Enqueue(new D { node = i, visited = vv, cost = cost, finished = d.finished });
            }
        }
        return int.MaxValue;
    }

    static int Calc(int v, int[,] adj) {
        int ans = int.MaxValue;
        for (int i = 0; i < v; i++) {
            ans = Math.Min(ans, Calc_1(i, v, adj));
        }
        return ans == int.MaxValue ? -1 : ans;
    }

    static void Main() {
        var ve = ReadInts();
        int v = ve[0], e = ve[1];

        var adj = new int[v, v];
        for (int i = 0; i < v; i++)
            for (int j = 0; j < v; j++)
                adj[i, j] = -1;

        for (int i = 0; i < e; i++) {
            var std = ReadInts();
            adj[std[0], std[1]] = std[2];
        }
        Console.WriteLine(Calc(v, adj));
    }
}