#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 18;
const int INF = (1 << 30);

int n, m, zero[NMAX], dp[NMAX][(1 << NMAX)];
vector < pair < int, int > > G[NMAX];

int main() {

    f >> n >> m;

    for(int i = 0;i < n;++i)
        zero[i] = INF;

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

    for(int t = 1;t <= m;++t) {
        int x, y, c;
        f >> x >> y >> c;

        G[x].push_back({y, c});

        if(y == 0)
            zero[x] = c;
    }

    dp[0][1] = 0;
    for(int stare = 1; stare < (1 << n);++stare) {
        for(int node = 0;node < n;++node) {
           if(dp[node][stare] != INF){ 
               for(auto& it : G[node]) {
                    int neighbor = it.first;
                    int cost     = it.second;

                    if(!(stare & (1 << neighbor))) {
                        int nextStare = stare + (1 << neighbor);
                        dp[neighbor][nextStare] = min(dp[neighbor][nextStare],
                                                      dp[node][stare] + cost);
                    }
               }
            }
        }
    }

    int sol{INF};
    for(int i = 1;i < n;++i) {
        if(zero[i] != INF && dp[i][(1 << n) - 1] != INF)
            sol = min(sol, dp[i][(1 << n) - 1] + zero[i]);
    }

    if(sol != INF)
        g << sol; 
    else 
        g << "Nu exista solutie";

    f.close();
    g.close();

    return 0;
}