#include <fstream>
#include <vector>
#include <cstring>
#define INF 0x3f3f3f3f

using namespace std;

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

int c[21][21];
int d[20][(1<<18)+1];
int stare_finala = 1;
vector<int> RV[21];
int n,m;
int nemo(int nod, int stare)
{
    if(d[nod][stare] != -1)
        return d[nod][stare];
    d[nod][stare] = INF;
    if(nod == 0)
    {
        if(stare == 0)
            return 0;
        return INF;
    }
    for(int i = 0; (1<<i) <= stare; i++)
        if( (1<<i) & stare && c[i][nod])
        {
            int r = nemo(i,stare-(1<<nod)) + c[i][nod];
            if(r < d[nod][stare])
                d[nod][stare] = r;
        }
    return d[nod][stare];
}


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

    memset(d,-1,sizeof(d));
    stare_finala = (1<<n) - 1;
    int sol = INF;
    d[0][1] = 0;
    for(vector<int>::iterator it = RV[0].begin(); it!= RV[0].end(); it++)
    {
        int r = nemo(*it, stare_finala) + c[*it][0];
        if(r < sol)
            sol = r;
    }
    if(sol == INF)
        fout<<"Nu exista solutie";
    else
        fout<<sol;

    fin.close();
    fout.close();
    return 0;
}