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

list<int> L[DIM];
list<int>::iterator it;

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

    f>>n>>m;
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++)
            A[j][i]=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);
                    }
                }
            }
        }
    }
    int sol=INF+11;
    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;
}