#include "bits/stdc++.h"
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
int a[20][20],dp[1048580][20];
int main ()
{
    int n,m,x,i,j,k,mask,y,c,min1;
    f>>n>>m;
    for (x=1;x<=m;x++)
    {
        f>>i>>j>>c;
        a[i][j]=c;
    }
    for (mask=1;mask<(1<<n);mask++)
        for (x=0;x<n;x++)
        dp[mask][x]=18000002;
    dp[1][0]=0;
    for (mask=1;mask<(1<<n);mask++)
    {
        for (x=0;x<n;x++)
        {
            if (mask&(1<<x))
            {
                for (y=0;y<n;y++)
                {
                    if (mask&(1<<y) && a[y][x]!=0)
                    {
                        dp[mask][x]=min(dp[mask][x],dp[mask-(1<<x)][y]+a[y][x]);
                    }
                }
            }
        }
    }
    min1=18000002;mask=(1<<n)-1;
    for (x=1;x<n;x++)
    {
        if (a[x][0]!=0)
        {
            min1=min (min1,dp[mask][x]+a[x][0]);
        }
    }
    if (min1<18000002) g<<min1;
        else g<<"Nu exista solutie";
    f.close ();
    g.close ();
    return 0;
}