#include <iostream>
#include <fstream>
#include <vector>
#define inf 999999999

using namespace std;

int n,m,cost[20][20],dp[20][262150];
vector<int>g[20];

void init()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<20;j++)
            cost[i][j]=inf;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(1<<n);j++)
            dp[i][j]=-1;
    }
    // for (int i = 1; i < n; i++)
        // dp[i][(1<<i) + 1] = cost[0][i];
    dp[0][1]=0;
}

void citire()
{
    ifstream fin("hamilton.in");
    fin>>n>>m;
    init();
    int x,y,c;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        g[y].push_back(x);
        cost[x][y]=c;
    }
}

void rez(int i,int j)
{
    if(dp[i][j] != -1)
        return;
    if(j&(1<<i)==0)
        return;
    int mini=inf;
    for(auto&x:g[i])
        if(j&(1<<x))
        {
            rez(x,j^(1<<i));
            int pre = dp[x][j^(1<<i)] + cost[x][i];
            if(mini > pre)
                mini = pre;
        }
    dp[i][j]=mini;
}

void afisare()
{
    int sol=inf;
    for(auto&v:g[0])
    {
        rez(v,(1<<n)-1);
        if(sol>dp[v][(1<<n)-1]+cost[v][0])
            sol=dp[v][(1<<n)-1]+cost[v][0];
    }
    ofstream fout("hamilton.out");
    if(sol==inf)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
}

int main()
{
    citire();
    afisare();
    return 0;
}