#include <fstream>
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int C[1<<18][20];
int D[20][20];
int pow2[20];
vector <int> V[20];
void initpow2()
{
    pow2[0]=1;
    for(int i=1;i<=18;i++)
        pow2[i]=pow2[i-1]*2;
}
int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    int n,m,a,b,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        D[a][b]=c;
        V[b].push_back(a);
    }
    initpow2();
    const int limit=(1<<n);
    for(int i=1;i<limit;i++)
        for(int j=0;j<n;j++)
            C[i][j]=INF;
    C[1][0]=0;
    for(int i=1;i<limit;i++)
        for(int j=0;j<n;j++)
            if(i&pow2[j])
                for(auto x:V[j])
                    if(i&pow2[x])
                        C[i][j]=min(C[i][j],C[i^pow2[j]][x]+D[x][j]);
    int SOL=INF;
    for(auto x:V[0])
    {
        SOL=min(SOL,C[limit-1][x]+D[x][0]);
    }
    if(SOL==INF)
        fout<<"Nu exista solutie";
    else
        fout<<SOL;
    return 0;
}