#include <fstream>
#define NMAX 20
#define INF 1000000000

using namespace std;

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

int n, m, cost, costmin;
int c[NMAX][NMAX];
int uz[NMAX];
int sol[NMAX], solmin[NMAX];

void citire();
void hamiltonian(int);

int main()
{
    int i;
    citire();
    sol[1]=1;
    uz[1]=1;
    costmin=INF;
    hamiltonian(2);
    if (costmin==INF)
        fout<<"Nu exista solutie\n";
    else
        fout<<costmin<<'\n';
    /*for(i=1; i<=n; i++)
        fout<<solmin[i]<<' ';*/
    return 0;
}
void citire()
{
    int i, j, x, y, cost;
    fin>>n>>m;
    for (i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i==j)
                c[i][j]=0;
            else
                c[i][j]=INF;
    for(i=1; i<=m; i++)
        {
        fin>>x>>y>>cost;
        c[x+1][y+1]=cost;
        }
}
void hamiltonian (int k)
{
    int i;
    if (cost>=costmin) return;
    if (k==n+1 && c[sol[n]][sol[1]]!=INF && costmin>cost+c[sol[n]][sol[1]])
        {
        costmin=cost+c[sol[n]][sol[1]];
        for(i=1; i<=n; i++)
            solmin[i]=sol[i];
        }
    else
        if(k<=n)
            for(i=2; i<=n; i++)
                if(uz[i]==0 && c[sol[k-1]][i]!=INF)
                    {
                    uz[i]=1;
                    cost=cost+c[sol[k-1]][i];
                    sol[k]=i;
                    hamiltonian(k+1);
                    cost=cost-c[sol[k-1]][i];
                    uz[i]=0;
                    }

}