#include <bits/stdc++.h>

const int oo=1e9;

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

priority_queue<pair<int,pair<int,int> > > Q;
int n,m,x,y,c,i,j,dist[20],dyn[1<<18][20];
vector<pair<int,int> > v[20];

int main()
{
    f>>n>>m;
    for(i=1;i<n;i++)dist[i]=oo;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        if(!y)
            dist[x]=c;
        else
            v[x].push_back({y,c});
    }
    int x=(1<<n)-1;
    for(i=0;i<=x;i++)
        for(j=0;j<n;j++)
            dyn[i][j]=oo;
    dyn[0][0]=0;
    Q.push({0,{0,0}});
    while(Q.size())
    {
        pair<int,pair<int,int> > nod=Q.top();
//        cout<<-nod.first<<' '<<nod.second.first<<' '<<nod.second.second<<'\n';
        Q.pop();
        if(dyn[nod.second.first][nod.second.second]!=(-nod.first))
            continue;
        int mask=nod.second.first,poz=nod.second.second;
        for(auto it:v[poz])
            if(!(mask&(1<<it.first)))
                if(dyn[mask|(1<<it.first)][it.first]>dyn[mask][poz]+it.second)
                {
                    dyn[mask|(1<<it.first)][it.first]=dyn[mask][poz]+it.second;
                    Q.push({-dyn[mask|(1<<it.first)][it.first],{mask|(1<<it.first),it.first}});
                }
    }
//    for(i=0;i<=x;i++)
//    {
//        for(j=0;j<n;j++)
//            if(dyn[i][j]!=oo)
//        {
//            int auy=i;
//            for(int k=0;k<n;k++)
//            {
//                g<<(auy&1);
//                auy>>=1;
//            }
//            g<<' '<<j<<' '<<dyn[i][j];
//            g<<'\n';
//        }
//    }
    int ans=oo;
    for(i=1;i<n;i++)
        ans=min(ans,dyn[x-1][i]+dist[i]);
    if(ans-oo)
        g<<ans;
    else
        g<<"Nu exista solutie";
    return 0;
}