#include <bits/stdc++.h>

using namespace std;

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

int n,m,v[20][20],rez[1<<20][20], INF = 1<<30, primul[1<<20][20];

int main()
{
    in>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,pret;
        in>>x>>y>>pret;
        v[x][y] = pret;
    }
    for(int i = 1;i < 1<<n;i++)
    {
        for(int j = 0;j < n;j++)
            rez[i][j] = INF;        /// initializez toata matricea cu infinit
    }
    rez[1][0] = 0;     /// aleg punctul de plecare (aleg sa plec mereu din 0)
    for(int mask = 1;mask < 1<<n;mask++)
    {
        for(int last = 0;last < n;last++)
        {
            if((mask&(1<<last)) != 0)          /// pentru fiecare masca iau pe rand care sa fie ultimul nod pe care l-am parcurs
            {
                for(int x = 0;x < n;x++)
/// pentru masca "mask" in care utltimul nod parcurs este "last", iau pe rand toate nodurile in care pot sa ma duc din "last"
                {
                    if(v[last][x] && (mask&(1<<x)) == 0)
                    {
                        int nr = mask|(1<<x);
                        rez[nr][x] = min(rez[nr][x], rez[mask][last] + v[last][x]);
                    }
                }
            }
        }
    }
    int mx = INF;
    for(int i = 1;i < n;i++)
    {
/// pentru masca in care toate nodurile sunt parcurse iau pe rand care sa fie ultimul not al matricei
        if(v[i][0])
            mx = min(mx,rez[(1<<n) -1][i] + v[i][0]);
    }
    if(mx == INF)
        out<<"Nu exista solutie";
    else
        out<<mx;

    return 0;
}