#include<fstream>
using namespace std;

struct nod
{
    int v,cost;
    nod *urm;
};

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

nod *lista[20];
int n, m, x[20], smin, viz[20];
int a[20][20];

void citire(int &n, int &m, nod *lista[], int a[20][20])
{
    int i,j,x,y,c;
    nod *p;
    cin>>n>>m;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            a[i][j]=20000000;
        }
    }
    for (i=0;i<n;i++) {lista[i]=0;  a[i][i]=0;}
    for (i=0;i<m;i++)
    {
        cin>>x>>y>>c;
        a[x][y]=c;
        p=new nod;
        p->v=y;
        p->cost=c;
        p->urm=lista[x];
        lista[x]=p;
    }
}

int verificare(int x[], int k, int smin, int s, int viz[])
{
    if (viz[x[k]]==1) return 0;
    if (s>=smin)return 0;
    if (k==n && a[x[n]][x[1]]==20000000) return 0;
    if (k==n && s+a[x[n]][x[1]]>=smin) return 0;
}

void back(int x[], int k, int n, int &smin, nod *lista[], int s, int viz[])
{
    nod *p;
    if (k==n+1)
    {
        smin=s+a[x[n]][x[1]];
    }
    else
    {
        for (p=lista[x[k-1]];p!=0;p=p->urm)
        {
            x[k]=p->v;
            if (verificare(x,k,smin,s+p->cost, viz))
            {
                viz[x[k]]=1;
                back(x,k+1,n,smin,lista,s+p->cost,viz);
                viz[x[k]]=0;
            }
        }
    }
}

int main()
{
    citire(n,m,lista,a);
    smin=20000000;
    x[1]=0;
    viz[0]=1;
    back(x,2,n,smin,lista, 0, viz);
    if (smin==20000000) cout<<"Nu exista solutie";
    else cout<<smin;
    cout.close();
    return 0;
}