#include <fstream>
#include <vector>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int NR=19;
const int VAL=(1 << 18)+5;
const int INF=1000000000;

int N, M, i, j, cost, A, B, C, conf;
int dp[NR][VAL], mch[NR][NR], ANS;
bool ok[NR][VAL];
bool gasit;
vector <int> Ginv[VAL];
vector <int> :: iterator it;

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B >> C;
        mch[A][B]=C;
        Ginv[B].push_back(A);
    }
    for (i=0; i<N; i++)
        ok[i][1 << i]=true;
    for (conf=1; conf<(1 << N); conf++)
    {
        for (i=0; i<N; i++)
        {
            if ((conf & (1 << i))==0 || conf==(1 << i))
                continue;
            for (it=Ginv[i].begin(); it!=Ginv[i].end(); it++)
            {
                if (ok[*it][conf-(1 << i)]==true)
                {
                    ok[i][conf]=true;
                    cost=dp[*it][conf-(1 << i)];
                    if (dp[i][conf]==0)
                        dp[i][conf]=cost+mch[*it][i];
                    else
                        dp[i][conf]=min(dp[i][conf], cost+mch[*it][i]);
                }
            }
        }
    }
    ANS=INF;
    for (i=0; i<N; i++)
        if (ok[i][(1 << N)-1]==true && mch[i][0]!=0)
            ANS=min(ANS, dp[i][(1 << N)-1]+mch[i][0]);
    if (ANS==INF)
        fout << "Nu exista solutie";
    else
        fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}