#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int NMAX = 19;
const int INF = (1<<29);

vector < pair<int,int> > v[NMAX];
int dp[NMAX][(1<<18)+10],drum_0[NMAX];

int main()
{
    int n,m,x,y,cost;
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> x >> y >> cost;
        v[x].push_back({y,cost});
        if(y==0) drum_0[x]=cost;
    }
    for(int st=1;st<(1<<n);st++)
        for(int i=0;i<n;i++)
            dp[i][st]=INF;
    dp[0][1]=0;
    for(int st=1;st<(1<<n);st++)
    {
        for(int i=0;i<n;i++)
        {
            int nod=(1<<i);
            if((st&nod)!=0)
            {
                for(int j=0;j<v[i].size();j++)
                {
                    int vecin=v[i][j].first;
                    if((st&(1<<vecin))==0)
                        dp[vecin][st+(1<<vecin)]=min(dp[vecin][st+(1<<vecin)],dp[i][st]+v[i][j].second);
                }
            }
        }
    }
    int rasp=INF;
    for(int i=0;i<n;i++)
    {
        if(drum_0[i]!=0)
            rasp=min(rasp,dp[i][(1<<n)-1]+drum_0[i]);
    }
    if(rasp==INF){
        fout << "Nu exista solutie";
        return 0;
    }
    fout << rasp;
    return 0;
}