#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct nod{
    int val;
    int cost;
};

const int nmax=18, inf=1e8;
vector<nod> G[nmax];
int dp[nmax][(1<<nmax)];

int main()
{
    for(int i=0; i<nmax; i++)
        for(int j=2; j<(1<<nmax); j++)
            dp[i][j]= inf;
    int n, m;
    fin >> n >> m;
    int x, y, z;
    for(int i=1; i<=m; i++)
    {
        fin >> x>> y >> z;
        G[x].push_back({y, z});
    }
    for(int conf=1; conf<(1<<n); conf++)
    {
         for(int v=0; v<n; v++)
            if((conf | (1<<v)) == conf)
                for(nod vecin: G[v])
                    if((conf | (1<<vecin.val)) != conf)
                       dp[vecin.val][conf|(1<<vecin.val)] = min(dp[vecin.val][conf|(1<<vecin.val)], dp[v][conf]+vecin.cost);
    }
    int ans=inf;
    for(int i=1; i<n; i++)
        for(auto vecin: G[i])
            if(vecin.val==0)
                ans=min(ans, dp[i][(1<<n)-1]+vecin.cost);
    if(ans==inf)
        fout << "Nu exista solutie";
    else
        fout << ans;
    return 0;
}