#include <cstdio>

#include<cstdlib>

#include <cstring>

#define INF 0x1f1f1f1f

#define min(a,b) (a) < (b) ? (a) : (b)

using namespace std;

int N,M;

int tri[12] = {0,1,3,9,27,81,243,729,2187,6561,19683,59049};

int dig[59050][11];  //dig[state][k_dig]  状态state的第k位是多少

int edge[11][11],dp[59050][11];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);

//    freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);

#endif // ONLINE_JUDGE

//

//    char stit[200];

//    for (int i=0;i<12;i++)

//    {

//        itoa(tri[i],stit,3);

//        puts(stit);

//    }

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

    {

        int t = i;

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

        {

            dig[i][j] = t%3;

            t /= 3;

            if(t == 0)break;

        }

    }

//    itoa(123,stit,3);

//    puts(stit);

//

//    puts("tst");

//    for(int j = 1; j <= 10; ++j)

//        printf("%d ",dig[123][j]);

    while(scanf("%d%d",&N,&M) != EOF)

    {

        memset(edge,INF,sizeof(edge));

        int a,b,c;

        int m2=M;

        while(M --)

        {

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

            if(c < edge[a][b])edge[a][b] = edge[b][a] = c;

        }

//        for (int i=1;i<=N;i++)

//        {

//            for (int j=1;j<=N;j++)

//                printf("%d ",edge[i][j]);

//            puts("");

//        }

        memset(dp,INF,sizeof(dp));

        for(int i = 1; i <= N; ++i)dp[tri[i]][i] = 0;

        int ans = INF;

        for(int S = 0; S < tri[N+1]; ++S)

        {

            int visit_all = 1;

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

            {

                if(dig[S][i] == 0)visit_all = 0;

                if(dp[S][i] == INF)continue;

                for(int j = 1; j <= N; ++j)

                {

                    if(i == j)continue;

                    if(edge[i][j] == INF ||dig[S][j] >= 2)continue;

                    int newS = S + tri[j];

                    dp[newS][j] =min(dp[newS][j],dp[S][i] + edge[i][j]);

                }

            }

            if(visit_all)

            {

                for(int j = 1; j <= N; ++j)

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

            }

        }

        if(ans == INF)

        {

            puts("-1");

            continue;

        }

        printf("%d\n",ans);

    }

    return 0;

}