#include <fstream>
#define DMAX 100
#define INF 2000000000
#include <cmath>

using namespace std;

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

void gen(int);
void afisare();

int n, m, M[DMAX][DMAX], lgtmin=INF, lgt;
int t[DMAX], tmin[DMAX];
bool use[DMAX];
int j;

void citire(), afisare(), bkt(int k);

void citire()
{
    int i;
    fin>>n>>m;
    while(m)
    {
        fin>>i>>j>>lgt;
        M[i+1][j+1]=lgt;
        m--;
    }
}

void bkt(int k)
{
    int i;
    if(k-1==n)
    {
        if(M[t[n]][1])
        {
            if(lgt+M[t[n]][1]<lgtmin)
            {
                lgtmin=lgt+M[t[n]][1];
                for(i=1;i<=n;i++)
                    tmin[i]=t[i];
            }
        }
    }
    else
        for(i=1;i<=n;i++)
            if(!use[i] && M[t[k-1]][i])
            {
                t[k]=i;use[i]=1;
                lgt+=M[t[k-1]][i];
                bkt(k+1);
                use[i]=0;
                lgt-=M[t[k-1]][i];
            }
}

int main()
{
    citire();
    t[1]=1;
    use[1]=1;
    bkt(2);
    afisare();
    return 0;
}


void afisare()
{
    if(lgtmin==INF)
        fout<<"Nu exista solutie.\n";
    else
        fout<<lgtmin-1<<'\n';
    fout.close();
}