#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 100000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
struct valtravel
{
    int cur,cost,taken;
};
int n,m,dp[(1<<19)-1][19],x,y,z,min1=INF,matcost[20][20];
vector <vector <int>> v(19),cost(19);
auto cmp=[](valtravel a,valtravel b)
{
    if (a.cost>b.cost)
        return 1;
    else if (a.cost==b.cost)
    {
        if (a.taken>b.taken)
        {
            return 1;
        }
        else if (a.taken==b.taken)
        {
            if (a.cur>b.cur)
                return 1;
            else return 0;
        }
        else return 0;
    }
    else return 0;
};
priority_queue <valtravel, std:: vector<valtravel>, decltype(cmp)> q(cmp);
void hamilton (int start)
{
    valtravel ins;
    ins.cur=start;
    ins.cost=0;
    ins.taken=(1<<start);
    q.push(ins);
    while (!q.empty())
    {
        valtravel a=q.top();
        q.pop();
        //cout<<a.cost<<'\n';
        if (a.taken==(1<<n)-1)
        {
            if (matcost[a.cur][start])
            {
                min1=min(min1,a.cost+matcost[a.cur][start]);
            }
           // cout<<a.cost<<' '<<a.cur<<' ';
           // cout<<'\n';
        }
        else
        {
        for (int j=0; j<v[a.cur].size(); j++)
        {
            int next=v[a.cur][j];
            if (!(a.taken & (1<<next)))
            {
                if (dp[a.taken+(1<<next)][next]>dp[a.taken][a.cur]+cost[a.cur][j] || dp[a.taken+(1<<next)][next]==0)
                {
                    dp[a.taken+(1<<next)][next]=dp[a.taken][a.cur]+cost[a.cur][j];
                    valtravel ins;
                    ins.cur=next;
                    ins.cost=dp[a.taken+(1<<next)][next];
                    ins.taken=a.taken+(1<<next);
                    q.push(ins);
                }
            }
        }
        }
    }
}
int main()
{
    f>>n>>m;
    for (int i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        v[x].push_back(y);
        cost[x].push_back(z);
        matcost[x][y]=z;
    }
    hamilton(1);
    if (min1==INF)
        g<<"Nu exista solutie";
    else
    g<<min1;
    return 0;
}