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
#include <bits/stdc++.h>
struct _route {
  int vertex_id;
  int unvisited;
  unsigned int cost;
};
struct _route *_r;
int visited_mask;
int route_index;
void route_init(int vertex_count, int route_count) {
  int i;
  visited_mask = 0;
  for (i = 0; i < vertex_count; i++) {
    visited_mask |= 1 << i;
  }
  route_index = 0;
  _r = (struct _route *)malloc(sizeof(struct _route) * route_count);
}
void route_delete() { free(_r); }
void route_visit(struct _route *r, int id) { r->unvisited &= ~(1 << id); }
int route_unvisited(struct _route *r, int id) {
  return r->unvisited & (1 << id);
}
struct _route *route_next() {
  struct _route *r;
  r = &_r[route_index++];
  return r;
}
struct _binheap {
  struct _route **e;
  int count;
};
struct _binheap *bh_new(int size) {
  struct _binheap *bh;
  bh = (struct _binheap *)malloc(sizeof(struct _binheap));
  bh->e = (struct _route **)malloc(sizeof(struct _route *) * size);
  bh->count = 0;
  return bh;
}
void bh_delete(struct _binheap *bh) {
  free(bh->e);
  free(bh);
}
void bh_percup(struct _binheap *bh, int i) {
  struct _route *vp, *vc, *tmp;
  while (i / 2 > 0) {
    vc = bh->e[i];
    vp = bh->e[i / 2];
    if (vc->cost < vp->cost) {
      bh->e[i / 2] = vc;
      bh->e[i] = vp;
    }
    i = i / 2;
  }
}
void bh_push(struct _binheap *bh, struct _route *v) {
  bh->count++;
  bh->e[bh->count] = v;
  bh_percup(bh, bh->count);
}
int bh_minchild(struct _binheap *bh, int i) {
  struct _route *vl, *vr;
  if (i * 2 + 1 > bh->count) {
    return i * 2;
  } else {
    vl = bh->e[i * 2];
    vr = bh->e[i * 2 + 1];
    if (vl->cost < vr->cost)
      return i * 2;
    else
      return i * 2 + 1;
  }
}
void bh_percdown(struct _binheap *bh, int i) {
  int ci;
  struct _route *vp, *vc, *tmp;
  while (i * 2 <= bh->count) {
    ci = bh_minchild(bh, i);
    vp = bh->e[i];
    vc = bh->e[ci];
    if (vp->cost > vc->cost) {
      bh->e[i] = vc;
      bh->e[ci] = vp;
    }
    i = ci;
  }
}
struct _route *bh_pop(struct _binheap *bh) {
  if (bh->count <= 0) return NULL;
  struct _route *v = bh->e[1];
  bh->e[1] = bh->e[bh->count];
  bh->count--;
  bh_percdown(bh, 1);
  return v;
}
void print_bh(struct _binheap *bh) {
  int i;
  struct _route *v;
  printf("bh[%d]:", bh->count);
  for (i = 1; i <= bh->count; i++) {
    v = bh->e[i];
    printf(" %d", v->cost);
  }
  printf("\n");
}
struct _edge {
  int dest;
  int distance;
  struct _edge *next;
};
struct _vertex {
  int id;
  struct _edge *edge;
};
int main() {
  struct _vertex *vertex, *v;
  struct _edge *edge, *e;
  struct _binheap *bh;
  struct _route *route, *r, *nr;
  int V, E, i, j, s, t, d, cost, next_v, dist;
  scanf("%d %d", &V, &E);
  vertex = (struct _vertex *)malloc(sizeof(struct _vertex) * V);
  edge = (struct _edge *)malloc(sizeof(struct _edge) * E);
  for (i = 0; i < V; i++) {
    v = &vertex[i];
    v->id = i;
    v->edge = NULL;
  }
  for (i = 0; i < E; i++) {
    scanf("%d %d %d", &s, &t, &d);
    e = &edge[i];
    e->dest = t;
    e->distance = d;
    e->next = vertex[s].edge;
    vertex[s].edge = e;
  }
  route_init(V, 1000000);
  bh = bh_new(1000000);
  r = route_next();
  r->unvisited = visited_mask;
  route_visit(r, 0);
  r->vertex_id = 0;
  r->cost = 0;
  bh_push(bh, r);
  cost = -1;
  while (bh->count) {
    r = bh_pop(bh);
    if (r->vertex_id == 0 && r->unvisited == 0) {
      cost = r->cost;
      break;
    }
    v = &vertex[r->vertex_id];
    e = v->edge;
    while (e != NULL) {
      next_v = e->dest;
      dist = e->distance;
      if (next_v == 0) {
        if (r->unvisited == 0) {
          nr = route_next();
          nr->vertex_id = next_v;
          nr->unvisited = r->unvisited;
          nr->cost = r->cost + dist;
          bh_push(bh, nr);
        }
      } else {
        if (route_unvisited(r, next_v)) {
          nr = route_next();
          nr->vertex_id = next_v;
          nr->unvisited = r->unvisited;
          route_visit(nr, next_v);
          nr->cost = r->cost + dist;
          bh_push(bh, nr);
        }
      }
      e = e->next;
    }
  }
  printf("%d\n", cost);
  bh_delete(bh);
  route_delete();
  return 0;
}
