#include<fstream>
using namespace std;
struct nod
{
int v, cost;
nod *urm;
};
nod *lista[19];
int n,m,x[100],y[100],smin;;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
void citire(int &n, int &m, nod *lista[])
{
int i,x,c,y;
nod* r;
cin >> n >> m;
for(i=0;i<n;i++)
lista[i]=0;
for(i=0;i<m;i++)
{
cin >> x >> y >> c;
r= new nod;
r->v=y;
r->cost=c;
r->urm=lista[x];
lista[x]=r;
}
}
void copiez(int y[],int x[],int n)
{
int i;
for(i=1;i<=n;i++)
y[i]=x[i];
}
int arc(int v1, int v2, nod *lista[])
{
nod *p;
p=lista[v1];
while(p!=0 && (p->v)!=v2)
p=p->urm;
if(p==0) return -1;
return (p->cost);
}
int suma(int x[],int n, nod* lista[])
{
int s=0, i;
for(i=2;i<=n;i++)
{
s=s+ arc(x[i-1], x[i],lista);
}
s=s+arc(x[n],x[1],lista);
return s;
}
int verificare(int x[], int k, int n, int smin, nod *lista[])
{
int i,s;
if(arc(x[k-1],x[k],lista)==-1) return 0;
s=0;
for(i=2;i<=k;i++)
{
s=s+arc(x[i-1],x[i],lista);
}
if(s>=smin) return 0;
if(k==n)
{
if(arc(x[n],x[1],lista)==-1) return 0;
s=s+arc(x[n],x[1],lista);
if(s>=smin) return 0;
}
for(i=1;i<=k-1;i++)
{
if(x[i]==x[k])
return 0;
}
return 1;
}
void back(int k, int x[], int y[], int n, int &smin, nod *lista[])
{
int i;
if(k==n+1)
{
smin=suma(x,n,lista);
// copiez(y,x,n);
}
else
{
for(i=1;i<=n-1;i++)
{
x[k]=i;
if(verificare(x,k,n,smin,lista)==1)
{
back(k+1,x,y,n,smin,lista);
}
}
}
}
int main()
{
smin=20000000;
citire(n,m,lista);
x[1]=0;
back(2,x,y,n,smin,lista);
if(smin==20000000)
{
cout << "Nu exista solutie";
}
else
{
cout << smin;
}
cout.close();
return 0;
}