#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

fstream f("hamilton.in");
ofstream g("hamilton.out");

long long int n,m,dp[20][(1<<18)+5],cost[20][20];
vector< int >vecini[20];

int main()
{
    f>>n>>m;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
     cost[i][j]=2000000005;
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        vecini[y].push_back(x);
        cost[x][y]=z;
    }

    for(int i=0; i<n; i++)
        for(int j=0; j<(1<<n); j++)
            dp[i][j]=2000000005;

    dp[0][1]=0;

    for(int i=0; i<(1<<n); i++)
    {
        for(int j=0; j<n; j++)
            if( (i&(1<<j)) )
            {
                for(int z=0; z<vecini[j].size(); z++)
                {
                    int nod=vecini[j][z];
                    if( (i&(1<<nod)) )
                    {
                       dp[j][i]=min(dp[j][i],dp[nod][(i^(1<<j))]+cost[nod][j]);
                    }
                }
            }
    }
    long long int sol=2000000005;

    for(int i=0;i<vecini[0].size();i++){
     int nod=vecini[0][i];
     sol=min(sol,dp[nod][(1<<n)-1]+cost[nod][0]);
    }
    if(sol==2000000005) g<<"Nu exista solutie";
    else g<<sol;

}