#include<bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int c[19][19];
int dp[(1<<19)][19];
const int K=1e9+1;
int main()
{
    int n,i,j,a,b,m;
    fin>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i!=j)
                c[i][j]=K;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        fin>>c[a][b];
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
        {
            dp[i][j]=K;
        }
    dp[1][0]=0;
    for(i=1;i<(1<<n);i+=2)
        for(j=0;j<n;j++)
            if((1<<j)&i)
            {
                for(int k=0;k<n;k++)
                    if(((1<<k)&i)==0&&c[j][k]!=K)
                    {
                        int mask=(i|(1<<k));
                        dp[mask][k]=min(dp[mask][k],dp[i][j]+c[j][k]);
                    }
            }

    m=K;
    for(i=1;i<n;i++)
        if(c[i][0]!=K&&m>c[i][0]+dp[(1<<n)-1][i])
            m=c[i][0]+dp[(1<<n)-1][i];
    if(m==K)
        fout<<"Nu exista solutie";
    else fout<<m;
    fin.close();
    fout.close();
    return 0;
}