#include <fstream>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,mat[20][20],cost[20][20],doi[21],dp[262150][22],verif;
int main()
{
    doi[0]=1;
    for(int i=1;i<=18;i++)
        doi[i]=doi[i-1]*2;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        mat[x][y]=1;
        fin>>cost[x][y];
    }
    ///caz de baza
    for(int i=1;i<n;i++)
    {
        if(mat[0][i])
            dp[(1<<i)|1][i]=cost[0][i];
    }
    /// y=ultimu elem, x=penultimu
    for(int mask=3;mask<=doi[n]-1;mask+=2)
    {
        for(int y=1;y<n;y++)
            if(mask&(1<<y))
            {
                int mask1=mask^(1<<y);
                int minim=10000000000;
                for(int x=1;x<n;x++)
                {
                    if(mask1&(1<<x))
                    {
                        if(mat[x][y])
                            minim=min(minim,dp[mask1][x]+cost[x][y]);
                    }
                }
                if(dp[mask][y]==0)
                    dp[mask][y]=minim;
            }
    }
    int minim=10000000000;
    for(int i=1;i<n;i++)
    {
        if(mat[i][0] && dp[doi[n]-1][i]!=minim)
        {
           minim=min(minim,dp[doi[n]-1][i]+cost[i][0]);
           verif=1;
        }
    }
    if(verif)
        fout<<minim;
    else
        fout<<"Nu exista solutie";
    return 0;
}