#include <iostream>
#include <fstream>
#define inf 1e9
#include <bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,a[20][20],c[263000][20],i,j,p,Min,m,x,y,C;
int main()
{
    f>>n>>m;
    for(i=0; i<=n; i++)
        for(j=0; j<=n; j++)
            a[i][j]=inf;
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>C;
        a[x][y]=C;
    }
    for(i=0; i<1<<n; i++)
        for(j=0; j<n; j++)
            c[i][j]=inf;
    c[1][0]=0;
    m=(1<<n)-1;
    for(i=0; i<=m; i++)
        for(j=0; j<n; j++)
        {
            if(i&(1<<j))
                for(p=0; p<n; p++)
                    if(a[p][j]!=inf)
                        if(c[i^(1<<j)][p]+a[p][j]<c[i][j])
                            c[i][j]=c[i^(1<<j)][p]+a[p][j];
        }
    Min=inf;
    for(i=1; i<n; i++)
        if(a[i][0]!=inf&&Min>c[m][i]+a[i][0])
            Min=c[m][i]+a[i][0];
    if(Min!=inf)
        g<<Min;
    else
        g<<"Nu exista solutie";
    return 0;
}