#include <bits/stdc++.h>
#define v first
#define c second
#define LIMIT 100000000
using namespace std;

vector<pair<int,int>> nodes[20];
int dp[(1 << 20)][20];

int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");

    int N,M,x,y,z;
    cin>>N>>M;
    for(int i = 0; i < M; i++)
    {
        cin>>x>>y>>z;
        nodes[x].push_back({y,z});
    }

    /// facem dp inainte
    /// dp[conf][nod] = costul minim de a ajunge in nod vizitand toate nodurile din conf
    /// dp[conf][nod] -> min(dp[conf | (1 << vecin)][vecin], dp[conf][nod] + cost[nod -> vecin])
    /// si vecinul sa nu fi fost deja in configuratie

    for(int conf = 1; conf < (1 << N); conf++)
    {
        for(int n = 0; n < N; n++)
        {
            dp[conf][n] = LIMIT;
        }
    }

    dp[1][0] = 0;
    for(int conf = 1; conf < (1 << N); conf++)
    {
        for(int n = 0; n < N; n++)
        {
            if((conf & (1 << n)) == 0)
            {
                continue;
            }
            for(auto vecin : nodes[n])
            {
                if((conf & (1 << vecin.v)) == 0)
                {
                    dp[(conf | (1 << vecin.v))][vecin.v] = min(dp[(conf | (1 << vecin.v))][vecin.v], dp[conf][n] + vecin.c);
                }
            }
        }
    }

    int sol = LIMIT;
    for(int n = 1; n < N; n++)
    {
        for(auto vecin : nodes[n])
        {
            if(vecin.v == 0)
            {
                sol = min(sol, dp[(1 << N) - 1][n] + vecin.c);
            }
        }
    }
    if(sol == LIMIT)
    {
        cout<<"Nu exista solutie";
    }
    else
    {
        cout<<sol;
    }
    return 0;
}