#include <fstream>
#define INF 1000000000
#define NMAX 20
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
struct drum {int x, c;};
void bkt(int k);
int t[20],us[20],lg,lgmin=INF,n;
drum H[NMAX][NMAX];
int nr[NMAX];
int v0[NMAX];
int main()
{
    int m,i,j,a,b,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        nr[a]++;
        H[a][nr[a]].x=b;
        H[a][nr[a]].c=c;
        if (b==0) v0[a]=c;
        //mat[b][a]=c;
    }
    t[1]=0; us[0]=1;
    bkt(2);
    if(lgmin==INF) fout<<"Nu exista solutie";
       else fout<<lgmin;
    return 0;
}

void bkt(int k)
{
    int i;
    if(lg>=lgmin) return;
    if(k==n+1)
        {if (v0[t[n]] && lg+v0[t[n]]<lgmin)
             lgmin=lg+v0[t[n]];
        }
        else
        for (i=1; i<=nr[t[k-1]];i++)
            if(!us[H[t[k-1]][i].x])
                {
                  t[k]=H[t[k-1]][i].x;
                  us[H[t[k-1]][i].x]=1;
                  lg+=H[t[k-1]][i].c;

                  bkt(k+1);

                  us[H[t[k-1]][i].x]=0;
                  lg-=H[t[k-1]][i].c;
                }

}