#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,c,sol,D[1<<18][20],C[20][20];
int main()
{
    int i,j,k;
    fin>>n>>m;
    for (i=0;i<m;++i)
    {
        fin>>x>>y>>c;
        C[x][y]=c;
//        v[x].push_back(y);
//        v[y].push_back(x);
    }
    memset(D,0x3f,sizeof(D));
    D[1][0]=0;
    for (i=3;i<(1<<n);++i,++i)
        for (j=1;j<n;++j)  // calc D[i][j]
            if (i&(1<<j))
            {
                for (k=0;k<n;++k)
                    if (k!=j && (i&(1<<k))!=0 && C[k][j]>0)
                        D[i][j]=min(D[i][j],D[i-(1<<j)][k]+C[k][j]);
            }

    sol=INF;
    for (i=1;i<n;++i)
        if (C[i][0]>0)
            sol=min(sol,D[(1<<n)-1][i]+C[i][0]);
    if (sol==INF)
        fout<<"Nu exista solutie\n";
    else
        fout<<sol<<"\n";
    return 0;
}