#include<iostream>
#include<fstream>
#include<vector>
#define inf 100000000
using namespace std;
vector<int>v[30];
int cost[23][23],d[1<<18+3][23],i,j,n,m,c,x,y,sol;
int main()
{

    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    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>>c;
        cost[x][y]=c;
        v[y].push_back(x);
    }

    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            d[i][j]=inf;

    d[1][0]=0;



    for(i=0;i<(1<<n);i++)
    {

        for(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]]+cost[v[j][k]][j]);

                }

            }
    }
    sol=inf;
    for(i=0;i<v[0].size();i++)
    {

        sol=min(sol,d[(1<<n)-1][v[0][i]]+cost[v[0][i]][0]);
    }
    if(sol==inf)
        cout<<"Nu exista solutie";
    else cout<<sol;
    return 0;
}