#include <fstream>
#include <vector>
#define INF 150000011
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m;
int D[1<<19][20],A[20][20];

vector<int> L[70];
vector<int>::iterator it;

int main(void){
    register int i,j,x,y,c,st,nod,sol;

    f>>n>>m;
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++)
            A[i][j]=INF;
        for(j=0;j<(1<<n);j++)
            D[j][i]=INF;
    }

    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        A[x][y]=min(A[x][y],c);
        L[x].push_back(y);
    }

    D[1][0]=0;
    for(st=3;st<(1<<n);st+=2){
        for(nod=0;nod<n;nod++){
            if(st&(1<<nod)){
                for(it=L[nod].begin();it!=L[nod].end();it++){
                    if(st&(1<<(*it))){
                        c=D[st-(1<<nod)][*it]+A[nod][*it];
                        D[st][nod]=min(D[st][nod],c);
                    }
                }
            }
        }
    }
    sol=INF+10;
    for(it=L[0].begin();it!=L[0].end();it++){
        sol=min(sol,D[(1<<n)-1][*it]+A[0][*it]);
    }
    if(sol>INF) g<<"Nu exista solutie";
    else g<<sol;
    f.close();
    g.close();
    return 0;
}