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

using namespace std;

vector <pair<int, int> > graf[18];
vector <pair<int, int> >::iterator it;
int n, m, d[18][1<<18], viz[18];

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[x].push_back(make_pair(y, c));
    }
    memset(d, inf, sizeof(d));
    d[0][1]=0;
}

void dfs(int drum)
{
    for(int nod=0;nod<n;nod++)
        if(drum&(1<<nod))
            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^(1<<nod)] + it->second);
}

void afisare()
{
    int minim=inf;
    for(it=graf[0].begin();it!=graf[0].end();it++)
        minim=min(minim, d[it->first][(1 << n) - 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();
    for(int i=0;i<(1<<n);i++)
        dfs(i);
    afisare();
    return 0;
}