#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define INF 200000
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector <int> vecini[20];
int cost[20][20];
int lantMin[270000][20];
int n,m,sol,i,j,x,y,c;
void afis()
{
    for(int i=0;i<1<<n;i++)
    {
        cout<<i<<" ";
        for(int j=0;j<n;j++)
            if(lantMin[i][j]==INF)
                cout<<"x ";
            else
                cout<<lantMin[i][j]<<" ";
            cout<<endl;
    }
    cout<<endl;
}
int main()
{
    fin>>n>>m;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
            cost[i][j]=INF;
    }
    for(i=0;i<1<<n;i++)
        for(j=0;j<=n;j++)
            lantMin[i][j]=INF;
    for(i=1;i<=m;i++)///.pt grafuri care incep la 1 se scade cu 1
    {
        fin>>x>>y;
        vecini[y].push_back(x);
        fin>>c;
        cost[x][y]=c;
    }

    lantMin[1][0]=0;
    //afis();
    for(i=0;i<1<<n;i++)
    {
        for(j=0;j<n;j++)
        if(i&&(1<<j))
        {
            for(int l=0;l<vecini[j].size();l++)
            {
                if(i&&(1<<vecini[j][l]))
                {
                    lantMin[i][j]=min(lantMin[i][j],
                                      lantMin[i^(1<<j)][vecini[j][l]]+cost[vecini[j][l]][j]);
                }
            }
        }
       // afis();
    }
    sol=INF;
    for(i=0;i<n;i++)
    {
        sol=min(sol,lantMin[(1<<n)-1][i]+cost[i][0]);
    }
    if(sol==INF)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
    return 0;
}