#include <bits/stdc++.h>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout("hamilton.out");
int A[20][20],Dp[262145][20],n; //Dp[mask][last]
constexpr int INFINIT = 2e9;

int main()
{
    //citirea matricei costurilor
    int m;
    fin>>n>>m;

    int ttn = 1<<n;
    for (int j=0;j<n;j++)
    {
        for (int i=0;i<n;i++)
            A[i][j] = INFINIT;

        for (int i=0;i<ttn;i++)
            Dp[i][j] = INFINIT;
    }
    //
    for (int i=0;i<m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        A[a][b]=c;
    }

    Dp[1][0] = 0; //includem nodul 0 mai intai.
    //Parcurgerea submultimilor
    for (int msk=3; msk<ttn; msk+=2) //asiguram ca bitul 0 nu este niciodata "clear"
    {
        for (int i=1;i<n;i++) //parcurgerea bitilor din bitmask
        {
            if ((msk & (1<<i)) == 0) continue; // daca bitul nu este in bitmask

            //se parcurg arcele (j, i) care exista
            for (int j=0; j<n; j++)
            {
                //daca nu avem arc...
                if (A[j][i] == INFINIT) continue;

                //actualizez DP-ul. Daca am gasit o cale mai scurta
                //intre (0)~~~>(j)-->(i) decat direct (0)~~~>(i), atunci
                //setez noul Dp
                Dp[msk][i] = min(Dp[msk][i], Dp[msk & ~(1<<i)][j] + A[j][i]);
            }
        }
    }

    int final = INFINIT;
    //Calculez solutia finala
    for (int i=1; i<n; i++)
    {
        if (A[i][0] == INFINIT) continue;
        final = min(final, Dp[ttn-1][i]+A[i][0]);
    }
    if (final == INFINIT)
        fout<<"Nu exista solutie";
    else
        fout<<final<<endl;
    return 0;
}