#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define inf 0x3f3f3f3f

 int State[];

 int visited[][];

 int dp[][];

 int map[][];

 int n,m;

 void Initiate()

 {

     State[]=;

     for(int i=;i<=;i++)

         State[i]=State[i-]*;

     for(int i=;i<=State[];i++){

         int tmp=i;

         for(int j=;j<=;j++){

             visited[i][j]=tmp%;

             tmp/=;

         }

     }

 }

 int main()

 {

     Initiate();

     int u,v,w,ans;

     while(~scanf("%d%d",&n,&m)){

         memset(dp,inf,sizeof(dp));

         memset(map,inf,sizeof(map));

         for(int i=;i<n;i++)dp[State[i]][i]=;

         while(m--){

             scanf("%d%d%d",&u,&v,&w);

             u--,v--;

             map[u][v]=map[v][u]=min(map[u][v],w);

         }

         ans=inf;

         for(int i=;i<State[n];i++){

             bool flag=true;

             for(int j=;j<n;j++){

                 if(visited[i][j]==)flag=false;//是否每个城市都至少走了1次

                 if(dp[i][j]==inf)continue;

                 for(int k=;k<n;k++)if(j!=k){

                     if(visited[i][k]>=)continue;

                     if(map[j][k]==inf)continue;

                     dp[i+State[k]][k]=min(dp[i+State[k]][k],dp[i][j]+map[j][k]);

                 }

             }

             if(flag){

                 for(int j=;j<n;j++){

                     ans=min(ans,dp[i][j]);

                 }

             }

         }

         if(ans==inf)ans=-;

         printf("%d\n",ans);

     }

     return ;

 }