#include<fstream>
#include<vector>
#include<cstring>
#define inf 0x7F7F7F7F
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

vector <int>G[20];
int cost[18][18],c[18][1<<18],n,m,x,y,C;
int main()
{
    memset(c,inf,sizeof(c));
    memset(cost,inf,sizeof(cost));
    f>>n>>m;
    for(int i=1;i<=m;++i){
        f>>x>>y>>C;
        G[x].push_back(y);
        cost[x][y]=C;
    }
    c[0][1]=0;
    for(int stare=1;stare<(1<<n);stare+=2){
        for(int i=0;i<n;++i){
            if(c[i][stare]!=inf){
                for(int j=0;j<(int)G[i].size();++j){
                    int vecin=G[i][j];
                    if((stare&(1<<vecin))==0){
                        int urmstare=stare+(1<<vecin);
                        c[vecin][urmstare]=min(c[vecin][urmstare],c[i][stare]+cost[i][vecin]);
                    }
                }
            }
        }
    }
    int Min=inf;
    for(int i=0;i<n;++i){
        if(cost[i][0]!=inf){
            if(c[i][(1<<n)-1]!=inf){
                Min=min(Min,cost[i][0]+c[i][(1<<n)-1]);
            }
        }
    }
    if(Min>=inf) g<<"Nu exista solutie";
    else g<<Min;
    return 0;
}