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

using namespace std;

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

void initC();
void citire();
void bkt(int k);
void fasol();
void afisare();

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

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

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

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

void bkt(int k)
{
int i;
if (cost>costmin) return;
if (k==n+1 && C[sol[n]][1]!=INF ) {cost+=C[sol[n]][1]; fasol(); cost-=C[sol[n]][1]; }
    else
    for (i=2;i<=n;i++)
         if (uz[i]==0 && C[ sol[k-1] ][ i ]!=INF /*&& C[ sol[k-1] ][ i ]!=0*/)
            {
             uz[i]=1; cost+=C[ sol[k-1] ][ i ];
             sol[k]=i;
             bkt(k+1);
             uz[i]=0; sol[k]=0; cost-=C[ sol[k-1] ][ i ];
            }
}

void fasol()
{
int i;
if (costmin>cost)
    {costmin=cost;
    for (i=1;i<=n;i++) solmin[i]=sol[i];
    }
    else return;
}

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