#include <fstream>
#include <vector>
#define DIM 18
#define INF 1e9
#define ff first
#define ss second

using namespace std;

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

int n, m, dp[(1<<DIM) + 1][DIM], x, y, c, minim = INF;

vector<pair<int, int> > graf[DIM];

bool test(int sub, int x){
    return !(sub & (1<<x));
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; ++ i){
        f>>x>>y>>c;
        graf[x].push_back(make_pair(y, c));
    }
    int kk = (1<<n) - 1;

    for(int i = 1; i <= kk; ++ i)
        for(int j = 0; j <= n; ++ j)
            dp[i][j] = INF;

    dp[1][0] = 0;

    for(int i = 1; i <= kk; ++ i)
        for(int j = 0; j < n; ++ j)
            for(int k = 0; k < graf[j].size(); ++ k){
                pair<int, int> nod = graf[j][k];
                if(test(i, nod.ff))
                        dp[i + (1<<nod.ff)][nod.ff] = min(dp[i + (1<<nod.ff)][nod.ff], dp[i][j] + nod.ss);
            }

    for(int i = 0; i < n; ++ i)
            for(int j = 0; j < graf[i].size(); ++ i){
                if(graf[i][j].ff == 0)
                    minim = min(minim, dp[kk][i] + graf[i][j].ss);
            }
    if(minim == INF)
        g<<"Nu exista solutie";
    else
        g<<minim;
    return 0;
}