#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
int n,m,x,y,c;
vector<pair<int,int>>adiacenta[20];
int dp[1<<20][20];
void citire()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        f >> x >> y >> c;
        adiacenta[x].push_back({y,c});
    }
}
void init()
{
    for(int i = 0;i<=(1<<n)-1;i++)
    {
        for(int j = 0;j<n;j++)
        {
            dp[i][j] = (1<<30)-1;
        }
    }
    // ciclul va incepe din nodul 0 asa ca doar pe el il initializam cu 0
    dp[1][0] = 0;
}
void calc_dp()
{
    // problema este asemanatoare cu problema morcovi
    for(int masca = 1;masca<=(1<<n)-1;masca++)
    {
        for(int nod_start = 0;nod_start<n;nod_start++)
        {
            if(masca & (1<<nod_start))
            {
                for(auto x : adiacenta[nod_start])
                {
                    if(masca & (1<<x.first))
                        dp[masca][nod_start] = min(dp[masca][nod_start],dp[masca ^ (1<<nod_start)][x.first]+x.second);
                }
            }
        }
    }
}
void gasire_rasp()
{
    int rasp = (1<<30)-1;
    // pentru a completa ciclul legam nodul 0 de vecinii sai si gasim costul minim
    for(auto x : adiacenta[0])
    {
        rasp = min(rasp,dp[(1<<n)-1][x.first]+ x.second);
    }
    (rasp==(1<<30)-1)?g << "Nu exista solutie": g << rasp;
}
int main()
{
    citire();
    init();
    calc_dp();
    gasire_rasp();
}