#include <fstream>
#define NMAX 20
#define INF 1000000000
using namespace std;

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

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

void citire ();
void initializare();
void afisare();
void ciclu(int k);

int main()
{
    citire();
    sol[1]=1;
    uz[1]=1;
    ciclu(2);
    afisare();
    return 0;
}

void citire ()
{
    int i, x, y, c;
    fin>>n>>m;
    initializare();
    for(i=1; i<=m; ++i)
    {
        fin>>x>>y>>c;
        C[x+1][y+1]=c;
    }
}

void initializare()
{
    int i, j;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            if(i==j)C[i][j]=0;
            else C[i][j]=INF;
}

void ciclu(int k)
{
    int i;
    if(costmin<cost)
        return;
    else if( k==n+1 && C[sol[n]][sol[1]]!=INF && costmin>cost+C[sol[n]][sol[1]])
    {
       for(i=1; i<=n; ++i)
        solmin[i]=sol[i];
       costmin=cost+C[sol[n]][sol[1]];
        return;
    }

    for(i=1; i<=n; ++i)
    if(C[sol[k-1]][i]!=INF && !uz[i])
    {
        cost+=C[sol[k-1]][i];
        sol[k]=i;
        uz[i]=1;
        ciclu(k+1);
        cost-=C[sol[k-1]][i];
        uz[i]=0;
    }

}

void afisare()
{
    //int i;
    if (costmin==INF)
        fout<<"Nu exista solutie\n";
    else
    {
        fout<<costmin<<'\n';
        /*for(i=1; i<=n; ++i)
            {
                fout<<solmin[i]-1<<' ';
            }*/
    }
    fout.close();
}