#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int nmax=19;
const int bitimax=(1<<nmax);
const int oo=1000000000;
int dp[bitimax][nmax],cost[nmax][nmax],n,m;
///dp[i][j]-costul minim al unui ciclu hamiltonian care se termina in nodul i.
inline void Read()
{
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=oo;
    for(int i=1;i<=m;i++)
    {
        int x,y,cs;
        fin>>x>>y>>cs;
        cost[x][y]=cs;
    }
}
inline void DP_Solve()
{
    int valmax=(1<<n)-1;
    for(int i=0;i<n;i++)
        for(int j=0;j<=valmax;j++)
                dp[j][i]=oo;
    dp[1][0]=0;
    for(int stare=1;stare<=valmax;stare++)
        for(int i=0;i<n;i++)
            if((stare&(1<<i)))
    {
        for(int j=0;j<n;j++)
        {
            if(!(stare&(1<<j)) && cost[i][j])///exista muchie i->j si nu am trecut prin nodul j(starea)
                dp[stare|(1<<j)][j]=min(dp[stare|(1<<j)][j],dp[stare][i]+cost[i][j]);
        }
    }
    int costfinal=oo;
    for(int i=0;i<n;i++)
        costfinal=min(costfinal,dp[valmax][i]+cost[i][0]);///adaugam si muchi i->0
    if(costfinal==oo)
         fout<<"Nu exista solutie\n";
    else fout<<costfinal<<"\n";
}
int main()
{
    Read();
    DP_Solve();
    fin.close();
    fout.close();
    return 0;
}