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>
#include <math.h>
#include <vector>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1 (i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef long l;
const ll l_INF = 1010101010101010;
const int INF = 1010101010;
const int dx[] = {-1,0,1,0,-1,-1,1,1};
const int dy[] = {0,-1,0,1,1,-1,1,-1};
int n,m,a,b,c,x[20][20];
int dp[20][1<<20];

int main(){
  rep(i,20){
    rep(j,20) x[i][j]=INF;
    rep(j,(1<<20)) dp[i][j]=INF;
  }
  cin>>n>>m;
  rep(i,m){
    cin>>a>>b>>c;
    x[a][b]=c;
  }
  dp[0][1]=0;
  rep(i,(1<<n)){
    rep(j,n){
      if(dp[j][i]<INF){
        rep(k,n){
          if((i/(1<<k))%2==0){
            int dist=dp[j][i]+x[j][k];
            int pos=i+(1<<k);
            if(dp[k][pos]>dist){
              dp[k][pos]=dist;
            }
          }
        }
      }
    }
  }
  int maxn=INF;
  rep(i,n) maxn=min(dp[i][(1<<n)-1]+x[i][0],maxn);
  if(maxn==INF) maxn=-1;
  cout<<maxn<<endl;
}

