#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second

const int NMAX = 18;
const int INF = 0x3f3f3f3f;

int n, m, dp[NMAX][1 << NMAX], graf[NMAX][NMAX];
vector<int> from, to;

void read()
{
    in >> n >> m;
    int x, y, c;
    for (int i = 1; i <= m; i++)
        in >> x >> y >> c, graf[x][y] = c;
    
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (!graf[i][j]) graf[i][j] = INF;
}

void TSP(int start)
{
    memset(dp, INF, sizeof dp);
    for (int i=0; i<n; i++)
        dp[i][1<<i] = graf[start][i];
        //cu mastile care incep in nodurile 1, 2, ..., n
        //defpat ne comportam de parca au inceput toate in 0 
        //si deci cand termin path-ul si am toate defapt o sa mai am si o muchie cu 0
    for (int mask = 1; mask < (1 << n) - 1; mask++)
    {
        from.clear();
        to.clear();
        for (int nod = 0; nod < n; nod++)
            (mask & (1<<nod)) ? from.pb(nod) : to.pb(nod);
        // daca nodul se afla in masca curenta il putem la from, altfel la to
        for (auto nodfrom : from)
            for (auto nodto : to)
                if (graf[nodfrom][nodto] != INF && dp[nodfrom][mask] != INF)
                    // exista muchie cu costul din matrice
                    // adaug nodul vecin la masca si il pun ca nod la care s-a ajuns ultimul
                        dp[nodto][mask | (1 << nodto)] = min(dp[nodto][mask | (1<<nodto)], dp[nodfrom][mask] + graf[nodfrom][nodto]);
        // il adaug in masca deci e masca din care se formeaza plus costul muchiei
    }
    dp[start][(1<<n)-1] == INF ? out<<"Nu exista solutie" : out<<dp[start][(1<<n)-1];
    //drum care se termina in start, dar a inceput tot in start, deci e ciclu
    
}

void solve()
{
    TSP(0);
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    read();
    solve();

    return 0;
}