#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int inf=1000000000;

int cost[20][20],c[262150][20],k;
vector<int> a[20];
int i,j,n,m,rez,x,y;
int main()
{
    fin>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cost[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        a[y].push_back(x);
        fin>>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(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]);
    rez=inf;
    for(i=0;i<a[0].size();i++)
        rez=min(rez,c[(1<<n)-1][a[0][i]]+cost[a[0][i]][0]);//, fout<<rez<<' ';
    if(rez==inf)
        fout<<"Nu exista solutie";
    else
        fout<<rez;
    return 0;
}