#include <fstream>
#include <cstdlib>
using namespace std;
ifstream  fin("hamilton.in");
ofstream fout("hamilton.out");
const int INF = 1e9;
int n,m,cost[20][20],x[20],costTotal,SS;  // numărul de noduri
int d[19][1<<17];
void bk1(int k1,int s1, int ct){
    if(k1==11){
        if(ct+cost[x[k1-1]][1]<d[x[2]][s1]){
            d[x[2]][s1]=ct+cost[x[k1-1]][1];
        }
    }
    else{
        for(int i=k1;i<=n;i++){
            swap(x[i],x[k1]);
            if(cost[x[k1-1]][x[k1]]<INF){
                bk1(k1+1,s1+(1<<(x[k1]-2)),ct+cost[x[k1-1]][x[k1]]);
            }
            swap(x[i],x[k1]);
        }
    }
}
void bk2(int k2, int s2, int ct){
    if(k2==n-9+1){
        int s1=(SS|s2)+(1<<(x[n-9]-1));
        if(ct+d[x[k2-1]][s1]<costTotal){
            costTotal=ct+d[x[k2-1]][s1];
        }
    }
    else{
        for(int i=k2;i<=n;i++){
            swap(x[i],x[k2]);
            if(cost[x[k2-1]][x[k2]]<INF){
                bk2(k2+1,s2+(1<<(x[k2]-1)),ct+cost[x[k2-1]][x[k2]]);
            }
            swap(x[i],x[k2]);
        }
    }
}
void bk(int k, int ct){
    if(k==n+1){
        ///
        if(ct+cost[x[n]][x[1]]<costTotal){
            costTotal=ct+cost[x[n]][x[1]];
        }
    }
    else{
        for(int i=k;i<=n;i++){
            swap(x[i],x[k]);
            int ok=1;
            if(cost[x[k-1]][x[k]]==INF || ct+cost[x[k-1]][x[k]]>costTotal){
                ok=0;
            }
            if(ok==1){
                bk(k+1,ct+cost[x[k-1]][x[k]]);
            }
            swap(x[i],x[k]);
        }
    }
}
int main() {
    fin >> n >> m;
    SS=(1<<(n-1))-1;///contine {2,3,...,n} micsorate cu 1 fiecare
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cost[i][j]=INF;
        }
        cost[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        cost[x+1][y+1]=c;
    }
    if(n<=11){
        costTotal=INF;
        for(int i=1;i<=n;i++){
            x[i]=i;
        }
        for(int i=n;i>=2;i--){
            int p=rand()%i+1;
            swap(x[p],x[i]);
        }
        bk(2,0);
        if(costTotal==INF){
            fout<<"Nu exista solutie";
            return 0;
        }
        fout << costTotal << endl;
        return 0;
    }
    for(int i=0;i<(1<<17);i++){
        for(int j=2;j<=n;j++){
            d[j][i]=INF;
        }
    }
    for(int i=2;i<=n;i++){
        x[i]=i;
    }
    for(int i=2;i<=n;i++){
        swap(x[2],x[i]);
        bk1(3,0,0);
        swap(x[2],x[i]);
    }
    for(int i=1;i<=n;i++){
        x[i]=i;
    }
    costTotal=INF;
    bk2(2,0,0);
    fout<<costTotal;
    return 0;
}