#include <iostream>
#include <fstream>
#include <queue>
#define pb push_back
#define f first
#define s second

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

struct triple
{
    int node, dist;
    long long stare;
    triple(int d,int n,long long s)
    {
        dist=d;
        node=n;
        stare=s;
    }
};

class cmp
{
public:
    bool operator()(triple a, triple b)
    {
        if(a.dist>b.dist)
            return 1;
        return 0;
    }
};

priority_queue <triple, vector<triple>,cmp > Q;
vector <pair<int, int> > G[19];
int n, m, i, x, y, c, mn, v;

int dij()
{
    Q.push(triple(0,0,1));
    while(!Q.empty())
    {
        int node=Q.top().node;
        int dist=Q.top().dist;
        long long stare=Q.top().stare;
        Q.pop();
        if(stare==(1<<n)-1)
        {
            for(unsigned int i=0;i<G[node].size();i++)
            {
                if(G[node][i].f==0)
                    return dist+G[node][i].s;
            }
        }
        for(unsigned int i=0;i<G[node].size();i++)
        {
            if(!(stare&(1<<G[node][i].f)))
            {
                Q.push(triple(dist+G[node][i].s,G[node][i].f,stare+(1<<G[node][i].f)));
            }
        }
    }
    return 0;
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        G[x].pb(make_pair(y,c));
    }
    v=dij();
    if(!v)
        fout<<"Nu exista solutie";
    else
        fout<<v;
    return 0;
}