#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 1<<27
using namespace std;
int dis[20][20],dp[59049][20],s[20];
int n,time[59049][20];
void init()
{
    int temp,i,j;
    s[1]=1;
    for(i=2; i<=n+1; i++)
        s[i]=s[i-1]*3;
    for(i=1; i<=s[n+1]; i++)
    {
        temp=i;
        for(j=1; j<=n; j++)
        {
            time[i][j]=temp%3;//模拟十进制取余求个数的方法。
            temp=temp/3;
        }
    }
}
int main()
{
    int i,a,b,c,k,m,j,ans,flag;
    while(~scanf("%d%d",&n,&m))
    {
        ans=inf;
        for(i=0; i<59049; i++)
        {
            for(j=0; j<20; j++)
                dp[i][j]=inf;
        }
        memset(s,0,sizeof(s));
        memset(time,0,sizeof(time));
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                if(i==j)
                    dis[i][j]=0;
                else
                    dis[i][j]=inf;
            }
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            dis[a][b]=dis[b][a]=min(dis[a][b],c);//防止有重边。
        }
          init();
        for(i=1; i<=n; i++)
            dp[s[i]][i]=0;//起点位置初始化为0.
        for(i=1; i<s[n+1]; i++)
        {
            flag=1;//各点是否全部已经到了。
            for(j=1; j<=n; j++)//当前到的这个城市。
            {
                if(time[i][j]==0)//该状态不可能都这个城市。
                {
                    flag=0;
                    continue;
                }
                for(k=1; k<=n; k++)//到下一个城市。
                {
                    if(time[i][k]==2||j==k)//如果等于2，就不可以。
                        continue;
                    int p=i+s[k];//到达下个城市的状态。
                dp[p][k]=min(dp[p][k],dp[i][j]+dis[j][k]);
                }
            }
            if(flag)
            {

                for(j=1; j<=n; j++)
                {
                 ans=min(ans,dp[i][j]);
                }
            }

        }
        if(ans==inf)
            printf("-1\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}
/*
4 5
1 4 1
1 2 1
1 3 2
4 3 10
2 3 10
*/