#include <fstream>

using namespace std;

long int a[20][20],sol[20],i,j,x,y,z,n,m,cost,minim;

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

inline long int ok(long int k)
{
    long int i;
   if (a[sol[k-1]][sol[k]]==0 &&k!=1) return 0;
   for (i=1;i<=k-1;i++)
   if (sol[k]==sol[i]) return 0;
    return 1;
}

inline void back(long int k)
{
    long int i,j;
    if (k>n) {
        if (a[sol[n]][sol[1]]!=0) {
        cost=0;
        for (j=1;j<=n-1;j++)
        cost=cost+a[sol[j]][sol[j+1]];
        cost=cost+a[sol[n]][sol[1]];
        if (cost<minim) minim=cost;
        }
    }
    else
    for (i=1;i<=n;i++) {
        sol[k]=i;
         if (ok(k)) back(k+1);
    }
}

int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>x>>y>>z;
        a[x+1][y+1]=z;
    }

    minim=1000000*18+5;
    back(1);
    if (minim==1000000*18+5) g<<"Nu exista solutie";
    else
    g<<minim;

    f.close();
    g.close();
    return 0;
}