#include <bits/stdc++.h>

using namespace std;

int state[],vis[][],dis[][];

int n,m,dp[][];

void init()//预处理三进制状态

{

    state[]=;

    for(int i=;i<=;i++)    state[i]=state[i-]*;//最多10个点，要处理到11

    for(int i=;i<=state[];i++)

    {

        int tmp=i;

        for(int j=;j<=;j++){// 把10位都处理一下

            vis[i][j]=tmp%;

            tmp/=;

        }

    }

}

int main()

{

    init();

    while(cin>>n>>m)

    {

        memset(dp,,sizeof(dp));

        memset(dis,,sizeof(dis));

        int inf=dp[][];

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

            dp[state[i]][i]=;

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

        {

            int l,r,w;

            cin>>l>>r>>w;

            dis[l][r]=dis[r][l]=min(dis[l][r],w);

        }

        int ans=inf;

        for(int i=;i<state[n+];i++)//枚举状态

        {

            bool flag=;

            for(int j=;j<=n;j++)//枚举状态的每一位

            {

                if(!vis[i][j])    flag=;//本状态没有达成目的

                if(dp[i][j]==inf)    continue;//没有前驱

                for(int k=;k<=n;k++)//枚举下一个节点

                {

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

                    if(dis[j][k]==inf)    continue;//没有路

                    dp[i+state[k]][k]=min(dp[i+state[k]][k],dp[i][j]+dis[j][k]);

                }

            }

            if(flag){

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

            }

        }

        if(ans==inf)    cout<<-<<endl;

        else    cout<<ans<<endl;

    }

}