#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;  // numărul de noduri
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;
    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;
    }
    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;
}