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>
using namespace std;
typedef long long ll;
const ll LINF = 1e18;
const int INF = 1e9;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int V;
int dist[20][20];
int dp[(1<<20)-1][15];
int seen[(1<<20)-1][20];

int rec(int bit, int v){    
    if(dp[bit][v]!=INF||seen[bit][v]==true)return dp[bit][v];
    seen[bit][v]=true;

    if(bit==0&&v==0)return dp[bit][v]=0;

    if(!(bit&(1<<v)))return INF;

    int pbit=bit&~(1<<v);

    rep(u,V){
        dp[bit][v]=min(rec(pbit,u)+dist[u][v],dp[bit][v]);
    }
    return dp[bit][v];
}

int main(){
    cin>>V;
    int E; cin>>E;
    rep(i,V)rep(j,V)dist[i][j]=INF;
    rep(i,E){
        int s,t,v; cin>>s>>t>>v;
        dist[s][t]=v;
    }

    int ans=INF;
    rep(i,1<<V)rep(j,V){
        dp[i][j]=INF;
        seen[i][j]=false;
    }
    ans=min(ans,rec((1<<V)-1,0));
    if(ans!=INF)cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}
