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 <iostream>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;
const int Max_Num=16;
const int INF=1000000;

int V, E;
int dist[Max_Num][Max_Num];
int dp[1<<Max_Num][Max_Num];

int bitDP(int start, int bit, int v){
  if(bit==((1<<V)-1)&&dist[v][start]==INF) return dp[bit][v]=INF;
  if(dp[bit][v]!=-1) return dp[bit][v];
  if(bit==(1<<start)) return dp[bit][start]=0;
  int bitprev=bit-(1<<v);
  int res=INF;
  rep(u,V){
    if(!(bitprev&(1<<u))||dist[u][v]==INF) continue;
    res=min(res,bitDP(start, bitprev, u)+dist[u][v]);
  }
  if(bit==((1<<V)-1)) return dp[bit][v]=res+dist[v][start];
  else return dp[bit][v]=res;
}

int main(){
  cin >> V >> E;
  rep(i,V){
    rep(j,V) dist[i][j]=INF;
  }
  rep(i,E){
    int s, t, d;
    cin >> s >> t >> d;
    dist[s][t]=d;
  }
  int ans=INF;
  rep(start,V){
    rep(i,1<<V){
      rep(j,V) dp[i][j]=-1;
    }
    rep(v,V) ans=min(ans,bitDP(start,((1<<V)-1),v));
  }
  if(ans==INF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}

