#include <bits/stdc++.h>
#define oo 1999000000

using namespace std;

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

int dist[20][20];
int n,m;
int dp[20][(1<<18)];

int main()
{
    int N;
    fin>>n>>m;
    N=(1<<n);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        dist[x][y]=c;
    }
    for(int i=0;i<n;i++)
        for(int masca=1;masca<N;masca+=2)
            dp[i][masca]=oo;
    dp[0][1]=0;
    for(int masca=3;masca<N;masca+=2)
        for(int i=1;i<n;i++)
            {
                int x=(masca^(1<<i));
                for(int j=0;j<n;j++)
                    if((masca & (1<<j)) && dist[j][i]>0)
                        dp[i][masca]=min(dp[i][masca],dp[j][x]+dist[j][i]);
            }
    int mn=oo;
    for(int i=1;i<n;i++)
        if(dp[i][N-1]+dist[i][0]<mn && dist[i][0]>0)
            mn=dp[i][N-1]+dist[i][0];
    if(mn==oo) fout<<"Nu exista solutie\n";
    else fout<<mn<<"\n";
    return 0;
}