#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
#define min(a, b) a<b?a:b
#define N 1<<19

using namespace std;

vector <pair<int, int> > graf[20];
vector <pair<int, int> >::iterator it;
int n, m, d[20][N], viz[20], lim;

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=0;i<m;i++)
    {
        int x, y, c;
        scanf("%d %d %d\n", &x, &y, &c);
        graf[y].push_back(make_pair(x, c));
    }
    for(int i=0;i<18;i++)
        for(int j=0;j<N;j++)
            d[i][j]=inf;
    d[0][1]=0;
}

void hamiltion()
{
    lim=1<<n;
    for(int drum=0;drum<lim;drum++)
    {
        for(int nod=0;nod<n;nod++)
        {
            int p=1<<nod;
            if(drum&p)
                for(it=graf[nod].begin();it!=graf[nod].end();it++)
                    if(drum^(1<<(it->first))==0)
                        d[nod][drum]=min(d[nod][drum], d[it->first][drum^p] + it->second);
        }
    }
}

void afisare()
{
    int minim=inf;
    for(it=graf[0].begin();it!=graf[0].end();it++)
        minim=min(minim, d[it->first][lim-1] + it->second);
    if(minim==inf)
        cout<<"Nu exista solutie";
    else
        cout<<minim;
}

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    citire();
    hamiltion();
    afisare();
    return 0;
}