#include<fstream>
#include<iostream>
#include<vector>
#define NMax 20
#define ConfMax 1<<18
#define INF 1<<30
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int N,M,Sol = INF;
int cost[NMax][NMax];
int DP[ConfMax + 5][NMax];

vector <int> VT[NMax];

void Read()
{
    fin>>N>>M;

    for(int i = 0 ; i < N ; ++i)
        for(int j = 0 ; j < N ; ++j)
            cost[i][j] = INF;

    for(int i = 1 ; i <= M ; ++i)
    {
        int x,y,c;    fin>>x>>y>>c;
        VT[y].push_back(x);
        cost[x][y] = c;
    }
}

void Solve()
{
    int Conf = (1<<N);

    for(int i = 0 ; i < Conf ; ++i)
        for(int j = 0 ; j < N ; ++j)
            DP[i][j] = INF;

    DP[1][0] = 0;

    for(int i = 0 ; i < Conf ; ++i)
        for(int j = 0 ; j < N ; ++j)
            if(i & (1<<j))
            {
                for(int k = 0 ; k < (int) VT[j].size() ; ++k)
                    if(i & (1<<VT[j][k]))
                        DP[i][j] = min(DP[i][j] , DP[i - (1<<j)][VT[j][k]] + cost[VT[j][k]][j]);
            }

    for(int i = 0 ; i < (int) VT[0].size() ; ++i)
        Sol = min(Sol,DP[Conf - 1][ VT[0][i] ] + cost[ VT[0][i] ][0]);
}

void Print()
{
    if(Sol == INF)  fout<<"Nu exista solutie\n";
    else    fout<<Sol<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();

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