#include <iostream>
#include <fstream>
#include <vector>

#define maxN 20

using namespace std;

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

int n,m,cost[maxN][maxN],best[1<<maxN][maxN];
vector <int> G[maxN];

int main()
{
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[y].push_back(x);
        cost[x][y]=c;
    }

    for (int i=0; i<=(1<<n); ++i)
        for (int j=0; j<n; ++j)
            best[i][j]=1<<30;

    best[1][0]=0;
    for (int i=0; i<(1<<n); ++i)
        for (int j=0; j<n; ++j)
    {
        if (!(i&(1<<j))) continue;
        for (int k=0; k<G[j].size(); ++k)
        {
            int nv=G[j][k];
            best[i][j]=min(best[i][j], best[i^(1<<j)][nv] + cost[nv][j]);
        }
    }

    int sol=1<<30;
    for (int i=0; i<G[0].size(); ++i)
        sol=min(sol, best[(1<<n)-1][G[0][i]] + cost[G[0][i]][0]);
    if (sol==1<<30) fout<<"Nu exista solutie";
    else fout<<sol;

    return 0;
}