#include <iostream>
#include <bits/stdc++.h>
#define VMAX 18
#define INF 2000000000
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");


int graf[VMAX][VMAX];
int dp[VMAX][1<<VMAX];

int xor_(int a, int b)
{
    return a|b-a&b;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>j>>k>>t;
        graf[j][k]=t;
        graf[k][t]=t;
    }

    for(i=0;i<n;i++)
    {
        for(int bitmask=0;bitmask< (1<<n);bitmask++)
        {
            dp[i][bitmask]=INF;
        }
    }
    dp[0][1]=0;
    for(int bitmask = 1; bitmask<(1<<n); bitmask++)
    {
        for(i=0;i<n;i++) // ultimul nod pe care il adaugam la un dp anterior pentru a obtine dp[masca]
        {
            if(bitmask & (1<<i)) // daca nodul i apartine drumului specificat de masca
            {
                for(j=0;j<n;j++) // ultimul dp de la care puteam ajunge
                {
                    if(i!=j && graf[i][j] && (bitmask && (1<<j)) && dp[i][bitmask]>dp[j][bitmask ^ (1<<i)] + graf[i][j])
                    {
                        dp[i][bitmask] = dp[j][bitmask ^ (1<<i)] + graf[i][j];
                    }
                }
            }
        }
    }

    minim=INF;
    for(i=0;i<n;i++)
    {
        if(graf[0][i])
            minim=min(minim,dp[i][(1<<n)-1]+graf[0][i]);
    }
    fout<<minim<<'\n';



    return 0;
}