#include <bits/stdc++.h>


using namespace std;


// #define at(x) operator[](x) // uncomment this for a slight speed-increase,


#define INF 0x3f3f3f
#define endl '\n'
#define PB push_back
#define Pints pair<int, int>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define vll vector<long long>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vvb vector<vector<bool>>
#define vvll vector<vector<long long>>
#define vPints vector<pair<int, int>>
#define vvPints vector<vector<pair<int, int>>> // for Dijkstra


#define pq priority_queue


#define hashmap unordered_map
#define dict unordered_map




using ull = unsigned long long;
using ll = long long;




ll add_mod(const ll a, const ll b, const int the_MOD) {
    ll res = (a + b) % the_MOD;
    return res;
}


ll substract_mod(const ll a, const ll b, const int the_MOD) {
    ll res = (a - b) % the_MOD;
    if (res < 0) {
        res += the_MOD;
    }
    return res;
}




ll multiply_mod(const ll a, const ll b, const int the_MOD) {
    ll res = ((a % the_MOD) * (b % the_MOD)) % the_MOD;
    return res;
}


void dijkstra (
                  const vvPints & adj_lists,
                  const int ID_of_start,
                  const int ID_of_end,
                  const int N
              )
{


    pq <Pints, vPints, greater<Pints>>   Q;    // pairs like: (distance, node_id), the .top() element (pair) has the smallest distance
    Q.push(make_pair(0, ID_of_start));


    vb visited (N + 1, false);
    visited[ID_of_start] = true;


    vi distances (N + 1, INF);
    distances[ID_of_start] = 0;


    vi previouses(N + 1, -100);


    while (Q.empty() == false) {


        Pints potentially_to_visit = Q.top();
        Q.pop();


        // int dist_of_potentially_to_visit = potentially_to_visit.first;
        int ID_of_potentially_to_visit = potentially_to_visit.second;


        if (visited[ID_of_potentially_to_visit] == false) {


            visited[ID_of_potentially_to_visit] = true;


            for (auto neigh: adj_lists[ID_of_potentially_to_visit]) {


                int neighbour_idx = neigh.second;
                int d = distances[neighbour_idx];


                if (d > distances[ID_of_potentially_to_visit] + neigh.first) {


                    distances[neighbour_idx] = distances[ID_of_potentially_to_visit] + neigh.first;
                    previouses[neighbour_idx] = ID_of_potentially_to_visit;


                    Q.push(make_pair(distances[neighbour_idx], neighbour_idx));


                }


            }


        }


    }
    // END while


    vi path;
    if (distances[ID_of_end] == INF) {
        cout << "END not reachable!" << endl;
        return;
    }
    else {
        for (int at = ID_of_end; at != -100; at = previouses[at]) {
            path.PB(at);
        }
    }


    reverse(path.begin(), path.end());


    for (const auto elem : path) {
        cout << elem << " ";
    }
    cout << endl;




}


int binary_search_2(const vector<int> & a, const int target) {


    int N = a.size();


    int L = 0, R = N - 1;


    int ans = -1;


    while (L <= R) {


        int mid = L + (R - L) / 2;


        if (a[mid] >= target) {
            ans = a[mid];
            R = mid - 1;
        }
        else { // a[mid] < target
            L = mid + 1;
        }


    }
    // END while-loop ()




    return ans;
}

void clear_dp(vector<vector<ll>> & dp, const int N) {

    for (int i = 0; i < dp.size(); i++) {
        for (int j = 0; j < dp[0].size(); j++) {
            dp.at(i).at(j) = INF;
        }
    }

    for (int i = 0; i < N; i++) {

        int S = 1 << i; // 2**i

        dp.at(S).at(i) = 0LL;

    }

}

void solve(const int test_ID) {

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

    int N, M;
    fin >> N >> M;

    ll costs[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            costs[i][j] = INF;
        }
    }

    for (int i = 0; i < M; i++) {
        int x, y, c;
        fin >> x >> y >> c;

        costs[x][y] = c;
    }
    
    // bitmask dp
    // =====================
    // dp[1 << N][N] as shape, N = total no. of nodes
    
    // dim 0: subsets
    // dim 1: end_node_ID

    vector<vector<ll>> dp (1 << N, vll (N, INF));

    // BC's
    // =========
    for (int i = 0; i < N; i++) {

        int S = 1 << i; // 2**i

        dp.at(S).at(i) = 0LL;

    }

    ll ans = INF;

    // Start the simulation 
    // =======================
    for (int start_node_ID = 0; start_node_ID < N; start_node_ID++) {

        for (int S = 1; S < (1 << N); S++) { // S = 0 ignored as that mask does not contain any nodes

            for (int end_node_ID = 0; end_node_ID < N; end_node_ID++) {

                if (
                       (  (S & (1 << start_node_ID)) == 0 ) ||   // if either of the nodes (either start or end)
                       (  (S & (1 << end_node_ID))   == 0 )      // is NOT in the set S, then skip this iteration
                                                            // because the definition of dp[S][i][j] is that it holds the minimum cost
                                                            // of a road from i to j which goes through all the nodes held by S
                                                            // and i = start_node_ID, fixed
                    )
                {
                    continue;
                }

                for (int v = 0; v < N; v++) {
                
                    if ( 
                            (costs[v][end_node_ID] == INF)   // if there is no edge from ``v`` to ``end_node_ID``
                                    || 
                            ( (S & (1 << v)) == 0 )   // if v does not belong to S
                        ) 
                    {
                        continue;
                    }
                                                                    
                    dp.at(S).at(end_node_ID) = min (
                                                        dp.at(S).at(end_node_ID),
                                                        dp.at(S ^ (1 << end_node_ID)).at(v) + costs[v][end_node_ID]
                                                    );
                
                }

            }

        }

        for (int end_node_ID = 0; end_node_ID < N; end_node_ID++) {

            if (costs[end_node_ID][start_node_ID] != INF) {
                ans = min(ans, dp.at((1 << N) - 1).at(end_node_ID) + costs[end_node_ID][start_node_ID]);
            }

        }

        clear_dp(dp, N);

    }

    

    if (ans != INF) {
        fout << ans << endl;
    }
    else {
        fout << "Nu exista solutie" << endl;
    }

}


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

    solve(1);

    return 0;
}