#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int kMaxNod=20;
const int kMaxM=310;
const int kInf=0x3f3f3f3f;

int dp[1<<19][kMaxNod];
int nodes,edges;
struct nod
{
    int to,cost;
    nod(int t,int c):to(t),cost(c){};
};
vector<nod> ad[kMaxNod];
int main()
{
    fin>>nodes>>edges;
    for(int i=1;i<=edges;++i)
    {
        int from,to,cost;
        fin>>from>>to>>cost;
        ad[to].emplace_back(from,cost);
    }

    for(int i=0; i<(1<<nodes); ++i)
        for(int j=0;j<nodes;++j)
            dp[i][j]=kInf;

    dp[1][0]=0;
    for(int i=0; i<(1<<nodes); ++i)
        for(int j=1; j<nodes; ++j)
            for(int k=0; k<ad[j].size(); ++k)
                if((i | (1 << ad[j][k].to)) == i)
                    dp[i][j]=min(dp[i][j],dp[i^(1<<j)][ad[j][k].to]+ad[j][k].cost);

    int rez=kInf;
    for(int i=0;i<ad[0].size();++i)
    {
        rez=min(rez,dp[(1<<nodes)-1][ad[0][i].to]+ad[0][i].cost);
    }
    if(rez==kInf)
        fout<<"Nu exista solutie";
    else
        fout<<rez;
    return 0;
}