#include <fstream>
#define IN "hamilton.in"
#define OUT "hamilton.out"
#define NMAX 105
#define INF 1000000000

using namespace std;

FILE * fin=fopen(IN, "r");
FILE * fout=fopen(OUT, "w");

int n, m, cost, costmin=INF;
int MC[NMAX][NMAX];
bool uz[NMAX];
int sol[NMAX], solmin[NMAX];

void citire()
{
    int i, j;
    int x, y, cost;
    fscanf(fin, "%d%d", &n, &m);

    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
            MC[i][j]=INF;
        MC[i][i]=0;
    }

    for (i=1; i<=m; i++)
    {
        fscanf(fin, "%d%d%d", &x, &y, &cost);
        ++x; ++y;
        MC[x][y]=cost;
    }
}

void solve(int k)
{
    int i;

    if (cost>costmin) return;

    if (k==n+1)
    {
        if (MC[sol[n]][1]==INF) return;

        cost+=MC[sol[n]][1];
        if (cost<costmin)
        {

            for (i=1; i<=n; i++)
                solmin[i]=sol[i];
            costmin=cost;
        }
        cost-=MC[sol[n]][1];
        return;
    }

    for (i=2; i<=n; i++)
        if (!uz[i] && MC[sol[k-1]][i]!=INF)
        {
            uz[i]=true;
            sol[k]=i;
            cost+=MC[sol[k-1]][i];
            solve(k+1);
            cost-=MC[sol[k-1]][i];
            uz[i]=false;
        }
}

void afisare()
{
    if (costmin==INF)
    {
        fprintf(fout, "Nu exista solutie\n");
        return;
    }
    fprintf(fout, "%d", costmin);
}

int main()
{
    citire();
    sol[1]=1;
    costmin=INF;
    solve(2);
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}