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;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        class Graph
        {
            internal int to, cost;

            public Graph(int t,int d)
            {
                to = t;
                cost = d;
            }
        }

        class Salesman
        {
            internal int pos, sumCost;
            internal bool[] visited;

            public Salesman(int V)
            {
                visited = new bool[V];
            }

            public Salesman(Salesman other)
            {
                pos = other.pos;
                sumCost = other.sumCost;

                int temp = other.visited.Length;
                visited = new bool[temp];
                other.visited.CopyTo(visited, 0);
            }
        }

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int V = int.Parse(input[0]);
            int E = int.Parse(input[1]);

            Dictionary<int, List<Graph>> G = new Dictionary<int, List<Graph>>();
            for (int i = 0; i < V; i++) G.Add(i, new List<Graph>());

            for(int i = 0; i < E; i++)
            {
                input = Console.ReadLine().Split(' ');
                int s = int.Parse(input[0]);
                int t = int.Parse(input[1]);
                int d = int.Parse(input[2]);

                G[s].Add(new Graph(t, d));
            }

            Queue<Salesman> que = new Queue<Salesman>();

            foreach (var g in G[0])
            {
                Salesman willEnq = new Salesman(V);
                int next = g.to;
                willEnq.pos = next;
                willEnq.sumCost += g.cost;
                willEnq.visited[next] = true;
                que.Enqueue(willEnq);
            }

            int minCost = int.MaxValue;

            while (que.Count > 0)
            {
                Salesman cur = que.Dequeue();

                if (!cur.visited.Contains(false))
                {
                    minCost = Math.Min(minCost, cur.sumCost);
                    continue;
                }
                
                foreach (var g in G[cur.pos])
                {
                    int next = g.to;
                    if (cur.visited[next] == true) continue;
                    if (next == 0 && cur.visited.Where(a => a == false).Count() > 1) continue;
                    
                    Salesman willEnq = new Salesman(cur);
                    willEnq.pos = next;
                    willEnq.sumCost += g.cost;
                    willEnq.visited[next] = true;
                    que.Enqueue(willEnq);
                }
            }
            Console.WriteLine(minCost != int.MaxValue ? minCost : -1);
        }
    }
}