#include <fstream>
#define nmax 20
#define inf 1000000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m, c[nmax][nmax];
int sol[nmax], solMin[nmax];
int cost, costMin;
bool uz[nmax];

void citire();
void bkt(int);
void actualizare();
void afisare();

int main(){
    citire();
    costMin=inf; sol[1]=1; uz[1]=1;
    bkt(2);
    afisare();
    return 0;
}

void citire(){
    //initializare costuri
    int i, j;
    for(i=1; i<=n; ++i)
        for(j=i+1; j<=n; ++j)
            c[i][j]=c[j][i]=inf;
    //--------------------
    int x, y, cost;
    fin>>n>>m;
    for(int i=1; i<=m; ++i){
        fin>>x>>y>>cost;
        c[++x][++y]=cost;
    }
}

void bkt(int k){
    if(cost>costMin) return;
    if(k==n+1 && c[sol[n]][1]!=inf) actualizare();
    else{
        for(int i=1; i<=n; ++i){
            if(!uz[i] && c[sol[k-1]][i]!=inf && c[sol[k-1]][i]){
                sol[k]=i;
                uz[i]=1; cost+=c[sol[k-1]][i];
                bkt(k+1);
                sol[k]=0;
                uz[i]=0; cost-=c[sol[k-1]][i];
            }
        }
    }
}

void actualizare(){
    costMin=cost;
    costMin+=c[sol[n]][1];
    for(int i=1; i<=n; ++i)
        solMin[i]=sol[i];
}

void afisare(){
    fout<<costMin<<'\n';
    fout.close();
}