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 <stdio.h>
const int N=20;
const int MAXN=1<<16;
const int INF=1e9+10;;
int min(int a,int b){return a>b?b:a;}
int main(){
    int n,dis[N][N],m,l,r,w,dp[MAXN][N],ans=INF,all;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)dis[i][j]=INF;
    while(m--){
        scanf("%d%d%d",&l,&r,&w);
        dis[l][r]=w;
    }
    all=1<<n;
    dp[0][0]=0;
    for(int i=1;i<all;i++)for(int j=1;j<n;j++)if(i&(1<<j)){
        if(i==1<<j)dp[i][j]=dis[0][j];
        else{
            dp[i][j]=INF;
            for(int k=0;k<n;k++)if(k!=j&&i&(1<<k))dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+dis[k][j]);
        }
    }
    for(int i=1;i<n;i++)ans=min(ans,dp[all-2][i]+dis[i][0]);
    if(ans==INF)printf("-1\n");
    else printf("%d\n",ans);
}
