#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define inf 0x3f3f3f3f

int State[];

int vis[][];

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++)  //点j在状态里出现的次数

        {

            vis[i][j]=tmp%;

            tmp/=;

        }

    }

}

int main()

{

    Initiate();

    int u,v,w,ans;

    #ifndef ONLINE_JUDGE

    freopen("1.in","r",stdin);

    #endif

    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(vis[i][j]==)    flag=false;//是否每个城市都至少走了1次

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

                for(int k=;k<n;k++)    //枚举另一点

                    if(j!=k)

                    {

                        if(vis[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 ;

}