#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#define NMAX 18
#define Exp ( (1<<18)+1)
#define INF (1<<30)

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m, cost[NMAX][NMAX], D[Exp][NMAX];

void read()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        f >>x>>y>>c;
        cost[x][y]=c;
    }
}

void solve()
{
    for(int road=0; road<(1<<n); ++road)
        for(int j=0; j<n; ++j) D[road][j] = INF;

    D[(1<<0)][0] = 0;

    for(int road=0;road<(1<<n);++road)
    {
        for(int j=0; j<n; ++j)
        {
            if (D[road][j]==INF) continue;
            for(int k=0; k<n; ++k)
            {
                if ( (road & (1<<k) ) == 0 )
                {
                    if ( cost[j][k] == 0) continue;
                    int new_road = road | (1<<k);
                    D[new_road][k] = min( D[new_road][k], D[road][j] + cost[j][k] );
                }
            }
        }
    }


    int Min = INF;

    for(int i=1; i<n; ++i)
    {
        if (D[(1<<n)-1][i] != INF && cost[i][0] != 0)
        {
            Min = min(Min, D[(1<<n)-1][i] + cost[i][0]);
        }
    }

    if (Min == INF)
    {
        g << "Nu exista solutie" << "\n";
    }
    else
    {
        g << Min << "\n";
    }
}

int main(){

    read();
    solve();
    return 0;

}