#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

int dp[20][300000];
int cost[20][20];

int main()
{
    int n,m;
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        cost[x][y]=c;
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][1] = 0;
    for(int conf=1; conf<(1<<n); conf+=2)
    {
        //out << conf << ": ";
        for(int last=0; last<n; last++)
        {
            for(int prv=0; prv<n; prv++)
            {
                if(prv!=last && (conf&(1<<last))!=0 && cost[prv][last]!=0)
                {
                    dp[last][conf]=min(dp[prv][conf-(1<<last)]+cost[prv][last],dp[last][conf]);
                    //out<<dp[last][conf]<<' ';
                }
            }
        }
        //out<<'\n';
    }
    int rez=0x3f3f3f3f;
    int configuratie=(1<<n)-1;
    for(int i=0;i<n;i++)
    {
        if(cost[i][0]!=0)
        {
            rez=min(dp[i][configuratie]+cost[i][0],rez);
        }
    }
    if(rez==0x3f3f3f3f)
    {
        out<<"Nu exista solutie";
    }
    else
    {
        out<<rez;
    }
}