#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[nmax][bitimax],cost[nmax][nmax],n,m;
vector<int>L[nmax];
queue<pair<int,int> >c;
///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;
        L[x].push_back(y);
        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[i][j]=oo;
    dp[0][1]=0;
    c.push({0,1});///val,starea
    while(!c.empty())
    {
        int x=c.front().first;
        int stare=c.front().second;
        c.pop();
        for(int i=0;i<L[x].size();i++)
        {
            int aux=L[x][i];
            if(!(stare&(1<<aux)))
            {
                int stare1=(stare|(1<<aux));
                if(dp[aux][stare1]>dp[x][stare]+cost[x][aux])
                {
                    dp[aux][stare1]=dp[x][stare]+cost[x][aux];
                    c.push({aux,stare1});
                }
            }
        }
    }
    int costfinal=oo;
    for(int i=0;i<n;i++)
        costfinal=min(costfinal,dp[i][valmax]+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;
}