#include <fstream>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m;
const int N=20;
int d[1<<19][20];
int X,Y,Z;
vector<pair<int,int>>a[N],b[N];
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>X>>Y>>Z;
        a[X].push_back({Y,Z});
        b[Y].push_back({X,Z});
    }
    int lg=(1<<n);
    for(int i=0;i<lg;i++)
        for(int j=0;j<n;j++)
            d[i][j]=1e9;
    d[1][0]=0;
    for(int i=1;i<lg;i++)
    {
        for(int j=0;j<n;j++)
            if((1<<j)&i)
            {
                for(auto x: b[j])
                    if((1<<x.x)&i)
                        d[i][j]=min(d[i][j],d[i^(1<<j)][x.x]+x.y);
            }
    }
    int mn=1e9;
    for(int i=0;i<n;i++)
    {
        for(auto x: a[i])
            if(x.x==0)
                mn=min(mn,d[lg-1][i]+x.y);
    }
    if(mn!=1e9)
    g<<mn;
    else
        g<<"Nu exista solutie";
    return 0;
}