#include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 inline ll read(){

     int x=,f=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 /***********************************************************/

 int n, m;     // n < = 10

 const int maxn = 6e4+;

 int d[][maxn];

 //用三进制形式来表示状态

 int dist[][];

 //表示路径

 int t[];

 int cnt, state[maxn];

 int temp;

 //判断S的三进制是否没有一个0

 bool legal(int S){

     bool ok = true;

     for(int i = ;i <= n-;i++){

         if(S% == ){

             ok = false;

             break;

         }

         S /= ;

     }

     return ok;

 }

 void init(){

     temp = ;

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

         t[i] = temp;

         temp *= ;

     }

 }

 //i点在集合S中是否出现了至少一次

 inline bool in(int i, int S){

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

         S /= ;

     if(S%) return true;

     else return false;

 }

 int dp(int i, int S){

     if(d[i][S] >= ) return d[i][S];

     int &ans = d[i][S];

     ans = 1e9;

     int S1 = S - t[i];

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

         if(j != i && in(j, S1) && dist[j][i] != -)

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

     }

     return ans;

 }

 int main(){

     init();

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

         int max_3 = ;

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

             max_3 += t[i];

         cnt = ;

         for(int S = max_3;S < t[n];S++){

             if(legal(S))

                 state[cnt++] = S;

         }

         memset(dist, -, sizeof(dist));

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

             int a, b, c;

             scanf("%d%d%d", &a, &b, &c);

             a--;b--;

             //更新长度

             if(dist[a][b] == - || dist[a][b] > c)

                 dist[a][b] = dist[b][a] = c;

         }

         memset(d, -, sizeof(d));

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

             d[i][t[i]] = ;

         int sum = dp(, max_3);

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

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

                 sum = min(sum, dp(i, state[j]));

             }

         }

         if(sum == 1e9) printf("-1\n");

         else printf("%d\n", sum);

     }

     return ;

 }