#include <bits/stdc++.h>
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
int n,m,sol,c[23][23],d[263003][23];
vector <int> v[23];
int main()
{
    f>>n>>m;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j) c[i][j]=100000000;
    }
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        v[y].push_back(x);
        f>>c[x][y];
    }
    for(int i=0;i<1<<n;++i)
    {
        for(int j=0;j<n;++j) d[i][j]=100000000;
    }
    d[1][0]=0;
    for(int i=0;i<(1<<n);++i)
    {
        for(int j=0;j<n;++j)
        {
            if(i&(1<<j))
            {
                for(int k=0;k<v[j].size();++k) if(i&(1<<v[j][k])) d[i][j]=min(d[i][j],d[i^(1<<j)][v[j][k]]+c[v[j][k]][j]);
            }
        }
    }
    sol=100000000;
    for(int i=0;i<v[0].size();++i) sol=min(sol,d[(1<<n)-1][v[0][i]]+c[v[0][i]][0]);
    if(sol==100000000) g<<"Nu exista solutie";
    else g<<sol;
    return 0;
}