#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");

ofstream fout("hamilton.out");

vector < pair <int, int> > G[20];

int dp[(1LL << 18)][19];

int cost[19][19];

int n, Q, x, y, z, i, j, mask, answer, node;

struct nod{

    int node, cost;

    bool operator < (nod x) const{

        return cost > x.cost;

    };

};

nod temp, current;

void Dijkstra(int start_node){

    priority_queue <nod> Q;

    temp.node = start_node;

    temp.cost = 0;

    cost[start_node][start_node] = 0;

    Q.push(temp);

    while(!Q.empty()){

        current = Q.top();

        Q.pop();

        for(vector < pair <int, int> > :: iterator k = G[current.node].begin() ; k != G[current.node].end() ; k++){

            if(cost[start_node][k -> first] > cost[start_node][current.node] + k -> second){

                cost[start_node][k -> first] = cost[start_node][current.node] + k -> second;

                temp.node = k -> first;

                temp.cost = cost[start_node][k -> first];

                Q.push(temp);

            }

        }

    }

}

int main(){

    fin >> n >> Q;

    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

            cost[i][j] = 1e9;

    while(Q--){

        fin >> x >> y >> z;

        ++x, ++y;

        cost[x][y] = z;

        //G[x].push_back(make_pair(y, z));

    }

/*
    for(i=1;i<=n;i++)

        Dijkstra(i);

*/

    answer = 1e9;

    for(node=1;node<=1;node++){

        for(mask = 1 ; mask <= (1LL << n) - 1 ; mask++)

            for(i=1;i<=n;i++)

                dp[mask][i] = 1e9;

        dp[(1LL << (node - 1))][node] = 0;

        for(mask = 1 ; mask <= (1LL << n) - 1 ; mask++){

            if(__builtin_popcount(mask) == 1)

                continue;

            for(i=0;i<n;i++)

                if((mask >> i) & 1)

                    for(j=0;j<n;j++)

                        if(((mask >> j) & 1) && i != j)

                            dp[mask][i + 1] = min(dp[mask][i + 1], dp[mask - (1LL << i)][j + 1] + cost[j + 1][i + 1]);

        }

        for(i=1;i<=n;i++)

            if(dp[(1LL << n) - 1][i] + cost[i][node] < answer){

                answer = dp[(1LL << n) - 1][i] + cost[i][node];

            }

    }


    if(answer == 1e9)

        fout << "Nu exista solutie";

    else fout << answer;

}