#include<fstream>
#include<vector>
#include<iostream>
#define Inf 100000000
using namespace std;


vector <int> Arc[20];
int N,M,cost[20][20],configuratie[263000][20],sol;



void citire() {

    ifstream in("hamilton.in");
    int i,x,y,c;
    in>>N>>M;
    for(i=1;i<=M;i++) {
        in>>x>>y>>c;
        Arc[y].push_back(x);
        cost[x][y]=c;
    }
    in.close();

}

void solve() {

    int i,j,k;
    for(i=0;i<=N;i++)
        for(j=0;j<=N;j++)
            if(!cost[i][j])
                cost[i][j]=Inf;
    for(i=0;i<(1<<N);i++)
        for(j=0;j<N;j++)
            configuratie[i][j]=Inf;

    configuratie[1][0]=0;
    for(i=0;i<(1<<N);i++)
        for(j=0;j<N;j++)
            if(i&(1<<j))
                for(k=0;k<Arc[j].size();k++)
                    if(i&(1<<Arc[j][k]))
                       configuratie[i][j]=min(configuratie[i][j], configuratie[i^(1<<j)][Arc[j][k]]+cost[Arc[j][k]][j]);
    sol=Inf;
    for(i=0;i<Arc[0].size();i++)
        sol=min(sol,configuratie[(1<<N)-1][Arc[0][i]]+cost[Arc[0][i]][0]);

}

void afisare() {

    ofstream out("hamilton.out");
    if(sol!=Inf)
        out<<sol<<'\n';
    else
        out<<"Nu exista solutie"<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();
    return 0;

}