#include <cstdio>
using namespace std;

 int M[19][19];
 int ST[19];
 int n,m,maxim=1000000;

 void citesc(){

    int x,y,c;
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&c);
        M[x][y] = c;

    }
 }

int succ(int k){

    if(ST[k]++ < n-1)
          return 1;
    else return 0;
}

int valid(int k){

    if(!M[ST[k-1]][ST[k]])
        return 0;
     else
            for(int i=1;i<k;i++)
                if(ST[i] == ST[k])
                    return 0;
    if(k==n && !M[1][ST[k]])
        return 0;
return 1;
}

void MAXX(){

    int sum=0;
    for(int i=1;i<n;i++){
        sum+=M[ST[i]][ST[i+1]];

}

    if(M[ST[1]][ST[n]])
sum+=M[ST[1]][ST[n]];
else sum+=M[ST[n]][ST[1]];

if(sum<maxim)
maxim = sum;

}

void back(int k){

    if(k==n+1) MAXX();
    else{

        ST[k] = 0;
        while(succ(k))
            if(valid(k))
                back(k+1);
    }
}

int main(){

    citesc();
ST[1] = 0;
ST[2] = 0;
back(2);
printf("%d",maxim);

return 0;
}