#include <fstream>
#include <vector>

using namespace std;

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

const int NR=20;
const int VAL=(1 << 18)+5;
const int INF=2000000000;

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