#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN=20;
const int MAXX=262150;
const int INF=100000000;

int n,m,sol,i,j,x,y;
int cost[MAXN][MAXN];
int c[MAXX][MAXN];
vector <int> a[MAXN];


int main()
{
    cin>>n>>m;

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cost[i][j]=INF;
        }
    }

    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        a[y].push_back(x);
        cin>>cost[x][y];
    }

    for(i=0;i<1<<n;i++)
    {
        for(j=0;j<n;j++)
        {
            c[i][j]=INF;
        }
    }

    c[1][0]=0;

    for(i=0;i<1<<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i & (1<<j))
            {
                for(size_t k=0; k<a[j].size();k++)
                {
                    if(i & (1<<a[j][k]))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][a[j][k]]+cost[a[j][k]][j]);
                }
            }
        }
    }

    sol=INF;
    for(size_t i=0;i<a[0].size();i++)
    {
        sol=min(sol,c[(1<<n)-1][a[0][i]]+cost[a[0][i]][0]);
    }

    if(sol==INF)
        cout<<"Nu exista solutie"<<'\n';
    else
        cout<<sol<<'\n';


    return 0;
}