#include <bits/stdc++.h>

using namespace std;

#define TITLE "hamilton"

ifstream f (TITLE".in");
ofstream g (TITLE".out");

#define MaxN 20
#define MaxDp 1<<18
#define INT_MAX 1<<30

vector<vector<int>> dp(MaxN,(vector<int>(MaxDp,INT_MAX)));
vector<vector<pair<int,int>>> Muchii(MaxN);

int n,m;

int main()
{
    f>>n>>m;
    while(m--)
    {
        int a,b,c;
        f>>a>>b>>c;
        Muchii[b].push_back({a,c});
    }
    int LengthDp=(1<<n);

    dp[0][1]=0;

    for(int i=3; i<LengthDp; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i & (1<<j))
            {
                int temp = i - (1<<j);
                for(pair<int,int> it : Muchii[j])
                {
                    if(temp & (1<<it.first))
                    {
                        dp[j][i] = min(dp[j][i] , dp[it.first][temp]+it.second);
                    }
                }
            }
        }
    }

    int answer=INT_MAX;
    for(auto it : Muchii[0])
    {
        answer=min(answer, dp[it.first][LengthDp-1]+it.second);
    }

    if(answer==INT_MAX)
        g<<"Nu exista solutie";
    else
        g<<answer;
    return 0;
}