#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<queue>

using namespace std;

int dp[60000][11];///dp[i][j]表示i状态下以j结尾的最短步数

int three[11];///three[i]表示3的i次方是多少

int digit[60000][11];///digit[i][j]表示状态i的第j位是什么数字（0,1,2）

int edge[15][15];  //记录两点之间路径的值

int n,m;

const int INF=0x3f3f3f3f;  

void init()

{

    three[0]=1;

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

        three[i]=three[i-1]*3;

    for(int i=0; i<three[10]; i++)

    {

        int tem=i;     //tem代表当前的状态序号

        for(int j=0; j<10; j++)

        {

            digit[i][j]=tem%3;    //将状态压缩的当前状态的每一位的实际情况计算出来

            tem/=3;

        }

    }

}  

int main()

{

    init();    //将每一状态的所有点对应实际情况预先打表处理

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

    {

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

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

                edge[i][j]=INF;  //两点距离初始化，为后面的去重做准备

        for(int i=0;i<three[n];i++)

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

                dp[i][j]=INF;      //因为最后要求的是最短距离，所以初始化为INF

        while(int i=0;i<m;i++)

        {

            int a,b,c;

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

            edge[a-1][b-1]=edge[b-1][a-1]=min(c,edge[a-1][b-1]);      //去重

        }

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

            dp[three[i]][i]=0;       //dp的初始化，将起点都找出来 ,所有点的标号为0~n-1

        int ans=INF;

        for(int j=0; j<three[n]; j++)     //枚举所有状态

        {

            bool flag=1;

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

            {

                if(digit[j][i]==0)flag=0;///只要三进制数中存在一个0，那么就说明还有点没有遍历完，就不能当做最终答案来求,即筛选掉那些不符合题意的状态

                if(dp[j][i]!=INF)

                    for(int k=0;k<n;k++)

                        if(edge[i][k]!=INF&&digit[j][k]!=2)///注意这个digit[j][k]!=2,因为如果j状态在k点已经走过两次了显然是不能继续往下走的

                            dp[j+three[k]][k]=min(dp[j][i]+edge[i][k],dp[j+three[k]][k]);

                        //更新加入edge[i][k]边的最小值,j+three[k]表示用当前状态j，加入edge[i][k]后，更新状态j+three[k]的值

            }

            if(flag)

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

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

        }

        if(ans>=INF)

            printf("-1\n");

        else

            cout<<ans<<endl;

    }

    return 0;

}