#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int c[19][19], D[(1<<18)][19];
vector<int>G[19];
const int INF=1e9;

int main()
{
    fin>>n>>m;
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j) c[i][j]=INF;
    }
    for(int i=1; i<=m; ++i)
    {
        int x, y, cost;
        fin>>x>>y>>cost;
        c[x][y]=cost;
        G[y].push_back(x);
    }
    for(int i=0; i<(1<<n); ++i)
    {
        for(int j=0; j<n; ++j) D[i][j]=INF;
    }
    D[1][0]=0;
    for(int i=0; i<(1<<n); ++i)
    {
        for(int j=0; j<n; ++j)
        {
            if(i & (1<<j))
            {
                for(auto it:G[j])
                {
                    if(i & (1<<it))
                        D[i][j]=min(D[i][j], D[i ^ (1<<j)][it]+c[it][j]);
                }
            }
        }
    }
    int sol=INF;
    for(auto it:G[0])
    {
        sol=min(sol, D[(1<<n)-1][it]+c[it][0]);
    }
    if(sol==INF) fout<<"Nu exista solutie\n";
    else fout<<sol<<"\n";
    return 0;
}