#include<fstream>
using namespace std;

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


const int NMAX = 18;
const int MASK = 1 << NMAX;
const int INF = 1e9;

int dp[MASK][NMAX],c[NMAX][NMAX];

void ini(int n ,int masca)
{
    for(int i = 0 ; i < n ; i++)
        {
            for(int j = 0 ; j < n ; j++)
                {
                    c[i][j] = INF;
                }
        }
    for(int i = 0 ; i < masca ; i++)
        {
            for(int j = 0 ; j < n ; j++)
                {
                    dp[i][j] = INF;
                }
        }
}

int main()
{
    int n,m,a,b,cost,masca;
    cin >> n >> m ; masca = 1 << n;
    ini(n,masca);

    for(int i = 0 ; i < m ; i++)
        {
            cin >> a >> b >> cost;
            c[a][b] = cost;
        }

    // stari : dp[m][i] retine costul minim pentru a ajunge cu confinguratia m in i incepand din nodul 1.
    /* tranzitii : dp[1][0] = 0; pentru dp[m][i] : pentru fiecare bit care nu e setat in configuratia lui m,
    fie acest bit u , daca exista muchia i - u , dp[m | (1 << u)][u] = min(el insusi, dp[m][i] + c[i][u]).

    la final , vom parcurge rezultatul pe linia finala a dp ului si vom vedea care este costul minim pentru un circuit hamiltonian
    */

    dp[1][0] = 0;
    for(int m = 1; m < (masca - 1)   ; m++)
        {
            for(int i = 1 ; i < n ; i++)
                {
                   if(dp[m][i] == INF)
                        continue;

                   for(int u = 1 ; u < n  ; u++)
                    {
                        if(~m & (1 << u))
                            {
                                int newmask = m | (1 << u);
                                dp[newmask][u] = min(dp[newmask][u],dp[m][i] + c[i][u]);
                            }
                    }
                }
        }

    int path = INF;
    for(int i = 1 ; i < n ; i++)
        {
            path = min(path,dp[masca - 1][i] + c[i][0]);
        }

    string rez = path != INF ? to_string(path) : "Nu exista solutie" ;

    cout << rez << endl;
    cin.close();
    cout.close();
    return 0 ; // superpeace


}