#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int,int> > graf[20] ;
bitset<20> bt ;
int n , m , sol = 1000001 ;

int min2(int a , int b)
{
    return a < b ? a : b ;
}

void DFS(int nod , int nr , int cost )
{
    bt[nod] = 1 ;
    for (int i = 0 ; i < graf[nod].size() ; i++ )
    {
        if ( graf[nod][i].first == 0 && nr == n )
            sol = min2(sol,cost+graf[nod][i].second) ;
        if ( bt[graf[nod][i].first] == 0 )
            DFS(graf[nod][i].first,nr+1,cost+graf[nod][i].second) ;
    }
    bt[nod] = 0 ;
}

int main()
{
    int x , y , nod , c;
    fin >> n >> m ;
    for (int i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> c ;
        graf[x].push_back(make_pair(y,c)) ;
        nod = x ;
    }
    DFS(0,1,0) ;
    if ( sol == 1000001 )
        fout << "Nu exista solutie";
    else
        fout << sol ;
}