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

using namespace std;

vector <int> graf[18];
int n, m, d[18][1<<18], c[18][18];

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

void dfs(int drum)
{
    for(int nod=0;nod<n;nod++)
    {
        int p=1<<nod;
        if(drum&p)
            for(int i=0;i<graf[nod].size();i++)
                if(drum^(1<<(graf[nod][i]))==0)
                    d[nod][drum]=min(d[nod][drum], d[graf[nod][i]][drum^p]+c[graf[nod][i]][nod]);
    }
}

void afisare()
{
    int minim=inf;
    int p=1<<n;
    for(int i=0;i<graf[0].size();i++)
        minim=min(minim, d[graf[0][i]][p-1]+c[graf[0][i]][0]);
    if(minim==inf)
        cout<<"Nu exista solutie";
    else
        cout<<minim;
}

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

    citire();
    int lim=1<<n;
    for(int i=0;i<lim;i++)
        dfs(i);
    afisare();
    return 0;
}