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 java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static class Graph {
        public final int V_NUM;
        public final int[][] edges;

        public Graph(int V_NUM) {
            this.V_NUM = V_NUM;
            this.edges = new int[V_NUM][V_NUM];
            for (int i = 0; i < V_NUM; i++) {
                Arrays.fill(this.edges[i], Integer.MAX_VALUE);
            }
        }

        public void setDist(int src, int dest, int dist) {
            this.edges[src][dest] = dist;
        }

    }

    public static class TSP {
        public final Graph g;
        long[][] dp;

        public TSP(Graph g) {
            this.g = g;
        }

        public long solve() {
            int N = g.V_NUM;
            dp = new long[1 << N][N];
            // init dp[][] with MAX
            for (int i = 0; i < dp.length; i++) {
                Arrays.fill(dp[i], -1);
            }

            long ret = recurse(0, 0);
            return ret == Integer.MAX_VALUE ? -1 : ret;
        }

        private long recurse(int state, int v) {
            int ALL = (1 << g.V_NUM) - 1;
            if (dp[state][v] >= 0) {
                return dp[state][v];
            }
            if (state == ALL && v == 0) {
                dp[state][v] = 0;
                return 0;
            }
            long res = Integer.MAX_VALUE;
            for (int u = 0; u < g.V_NUM; u++) {
                if ((state & (1 << u)) == 0) {
                    res = Math.min(res, recurse(state | 1 << u, u) + g.edges[v][u]);
                }
            }
            dp[state][v] = res;
            return res;

        }

    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int E = in.nextInt();
        Graph g = new Graph(V);
        while (E > 0) {
            int src = in.nextInt();
            int dest = in.nextInt();
            int dist = in.nextInt();
            g.setDist(src, dest, dist);
            E--;
        }
        System.out.println(new TSP(g).solve());
    }
}
