#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int N=18,MAX=1<<18,inf=2e9;
struct elem
{
    int nod,cost;
};
int n,m,i,j,x,y,c,d[N][MAX];
vector<elem> rev[N];
void init()
{
    for(j=0;j<(1<<n);++j)
    for(i=0;i<n;++i)
        d[i][j]=inf;
}
void read()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        rev[y].push_back({x,c});
    }
}
void solve()
{
    d[0][1]=0;
    for(j=2;j<(1<<n);++j)
    {
        for(i=1;i<n;++i)
        {
            if(!(j&(1<<i))) continue;
            for(auto e:rev[i])
            {
                int y=e.nod;
                int c=e.cost;
                d[i][j]=min(d[i][j],min(inf,d[y][j^(1<<i)]+c));
            }
        }
    }
}
int print()
{
    int mn=inf;
    if(n==1) return 0;
    for(auto e:rev[0])
    {
        int y=e.nod;
        int c=e.cost;
        mn=min(mn,d[y][(1<<n)-1]+c);
    }
    if(mn==inf)
    {
        fout<<"Nu exista solutie";
        exit(0);
    }
    return mn;
}
int main()
{
    read();
    init();
    solve();
    fout<<print();
    return 0;
}