#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int oo = 2e9;
vector <pair <int, int> > G [20];
int v[20];
int sol = oo;
int N, M;

void DEFEU (int nod, int cost, int cnt)
{
    v[nod] = 1;
    //cout<<"Nod: "<<nod<<", cnt: "<<cnt<<"\n";
    //cout<<G[nod].size()<<"\n";
    for(int i = 0; i < G[nod].size(); ++i)
    {
        if(!v[G[nod][i].first])
            DEFEU(G[nod][i].first, cost + G[nod][i].second, cnt + 1);
        //else
        //    cout<<"Incerc sa merg de pe nodul "<<nod<<" pe nodul "<<G[nod][i].first<<", dar e deja vizitat\n";
        if(cnt == N && G[nod][i].first == 0) //avem n noduri in ciclu si urmatorul nod in lista de vecini e chiar 0 (inceputul)
        {

            sol = min (sol, cost + G[nod][i].second);
            //cout<<"AM GASIT O SOLUTIE DE "<<sol<<"\n";
        }
    }
    v[nod] = 0;
}

int main()
{
    ifstream in ("hamilton.in");
    ofstream out ("hamilton.out");

    int x, y, c;

    in>>N>>M;
    for (int i = 0; i < M; ++i)
    {
        in>>x>>y>>c;
        G[x].push_back(make_pair(y, c));
    }

    DEFEU(0, 0, 1);

    if (sol == oo)
        out<<"Nu exista solutie\n";
    else
        out<<sol;

    return 0;
}