/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

const int inf=(1<<30);
vector<int> nodes[18];
int cost[18][18];
int dp[18][(1<<18)];

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,i,j,u,v,c,mask,ans;
    fin >> n >> m;
    for (i=0;i<n;i++)
    {
         for (j=0;j<n;j++)
         {
              cost[i][j]=inf;
         }
    }
    for (i=1; i<=m; i++)
    {
        fin >> u >> v >> c;
        nodes[v].push_back(u);
        cost[u][v]=c;
    }
    for (mask=0; mask<(1<<n); mask++)
    {
        for (i=0; i<n; i++)
        {
            dp[i][mask]=inf;
        }
    }
    dp[0][1]=0;
    for (mask=0; mask<(1<<n); mask++)
    {
        for (i=0; i<n; i++)
        {
            if (mask&(1<<i))
            {
                for (auto next : nodes[i])
                {
                    if (mask&(1<<next))
                    {
                        dp[i][mask]=min(dp[i][mask],dp[next][mask^(1<<i)]+cost[next][i]);
                    }
                }
            }
        }
    }
    ans=inf;
    for (auto next : nodes[0])
    {
         ans=min(ans,dp[next][(1<<n)-1]+cost[next][0]);
    }
    if (ans!=inf)
    fout << ans;
    else
    fout << "Nu exista solutie";
}