#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
#define mp make_pair
using namespace std;

int dp[20][(1<<18)+5],cost[20][20];
bool drum[20][20];


int main()
{
    int n,m,rez=1<<30;
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    int x=(1<<n);
    memset(dp,127,sizeof(dp));
    for(;m;--m)
    {
        int a,b,c;
        f>>a>>b>>c;
        drum[a][b]=true;
        cost[a][b]=c;
    }
    dp[0][1]=0;
      for(int j=0;j<x;++j)
      {
         for(int i=0;i<n;++i)
         {
            for(int d=0;d<n;++d)
            if(drum[i][d])
            {
                int next_nod= d;
                if( ((1<<next_nod) & j)==0)
                    dp[next_nod][ (1<<next_nod) | j]=min( dp[next_nod][ (1<<next_nod) | j] , dp[i][j] + cost[i][next_nod]);
            }
          }
      }

    for(int i=1;i<n;++i)
    {
        if(drum[i][0])
            rez=min(rez,dp[i][x-1]+cost[i][0]);
    }
    if(rez==1<<30)
        g<<"Nu exista solutie\n";
        else
            g<<rez;
    return 0;
}