#include<fstream>
#include<vector>
#include<cstring>
#define inf 0x7f7f7f7f
using namespace std;
vector<pair<int, int> >L[18];
int n, m, x, y, z, M[18], D[1<<18][18], nod, vecin, cost, stare, urmStare, sol, i;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int main()
{
    memset(M, 127, sizeof(M));
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
        if(y==0)
            M[x]=z;
    }
    memset(D, 127, sizeof(D));
    D[1][0]=0;
    for(stare=1; stare<(1<<n); stare+=2)
    {
        for(nod=0; nod<n; nod++)
        {
            if(D[stare][nod]!=inf)
            {
                for(i=0; i<L[nod].size(); i++)
                {
                    vecin=L[nod][i].first;
                    cost=L[nod][i].second;
                    if((stare&(1<<vecin))==0)
                    {
                        urmStare=stare+(1<<vecin);
                        if(D[urmStare][vecin]>D[stare][nod]+cost)
                            D[urmStare][vecin]=D[stare][nod]+cost;
                    }
                }
            }
        }
    }
    sol=inf;
    for(i=1; i<n; i++)
    {
        if(M[i]!=inf && D[(1<<n)-1][i]!=inf)
            sol=min(sol, M[i]+D[(1<<n)-1][i]);
    }
    sol!=inf?out<<sol:out<<"Nu exista solutie";
    return 0;
}