#include <algorithm>
#include <fstream>
#include <vector>
#include <cstring>

#define inf 0x3f3f3f3f

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

vector<int>g[20];
int n, m, x, y;
int dp[20][(1<<18)+1], cost[20][20];

int main()
{
    fin>>n>>m;
    memset(cost,inf,sizeof(cost));
    for(int i = 1; i<= m; i++ )
    {
        fin>>x>>y;
        fin>>cost[x][y];
        g[y].push_back(x);
    }
    memset(dp,inf,sizeof(dp));
    dp[0][1]=0;
    for(int conf = 1; conf<(1<<n); conf++ )
    {
        for(int i = 0; i<n; i++ )
        {
            if(conf&(1<<i))
            {
                for(vector<int>::iterator it=g[i].begin(); it<g[i].end(); it++ )
                {
                    if(conf & (1<<(*it)) )
                        dp[i][conf]=min(dp[i][conf],dp[*it][conf^(1<<i)]+cost[*it][i]);
                }
            }
        }
    }
    int sol=inf;
    for(vector<int>::iterator it=g[0].begin(); it<g[0].end(); it++ )
        sol=min(sol,dp[*it][(1<<n)-1]+cost[*it][0]);
    if(sol==inf)
        fout<<"Nu exista solutie";
    else fout<<sol;
    fin.close();
    fout.close();
    return 0;
}