#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=18;
const long long INF=4e18;

int n,m;
vector<pair<int,int>> v[NMAX+2];

long long dp[1<<NMAX+2][NMAX+2];

void citire()
{
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;

        v[x].push_back({y,c});
    }
}

void rezolvare()
{
    int total=(1<<n);

    for(int i=0; i<total; i++)
        for(int j=0; j<n; j++)
            dp[i][j]=INF;

    dp[1][0]=0;

    for(int mask=1; mask<total; mask++)
    {
        for(int nod=0; nod<n; nod++)
        {
            if(dp[mask][nod]==INF)
                continue;

            for(auto x:v[nod])
            {
                int vec=x.first;
                int cost=x.second;

                if(mask & (1<<vec))
                    continue;

                int nmask=mask | (1<<vec);

                dp[nmask][vec]=min(dp[nmask][vec],dp[mask][nod]+cost);
            }
        }
    }
}

void afisare()
{
    int mask=(1<<n)-1;
    long long ans=INF;

    for(int i=1; i<n; i++)
    {
        for(auto x:v[i])
        {
            int vec=x.first;
            int cost=x.second;

            if(vec==0)
                ans=min(ans,dp[mask][i]+cost);
        }
    }

    if(ans==INF)
        fout<<"Nu exista solutie";
    else
        fout<<ans;
}

int main()
{
    citire();
    rezolvare();
    afisare();

    return 0;
}