#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 solve(const int test_ID) {

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

    int N, M;
    // cin >> N >> M;
    fin >> N >> M;

    // vvPints adj_lists(N, vPints ());  // adj_lists[i] contains pairs of type: (to_node_ID, cost_from_node_i_to_to_node_ID)
    //                                                                             // (ID, cost of the edge)
    
    // for (int i = 0; i < M; i++) {

    //     int x, y, c;
    //     adj_lists.at(x).PB(make_pair(y, c));

    // }

    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;
        // cin >> x >> y >> c;
        fin >> x >> y >> c;

        costs[x][y] = c;

    }
    
    // bitmask dp
    // =====================
    // dp[1 << N][N][N]  as shape, N = total no. of nodes
    
    vector<vector<vector<ll>>> dp ( 1 << N,  vector<vector<ll>> (N, vector<ll> (N, INF)));
    // dim 0: subsets
    // dim 1: start_node_ID
    // dim 2: end_node_ID


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

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

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


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

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

            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
                    )
                {
                    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[S][start_node_ID][end_node_ID] = min(
                                                              dp[S][start_node_ID][end_node_ID],
                                                              dp[S ^ (1 << end_node_ID)][start_node_ID][v] + costs[v][end_node_ID]
                                                          );
                
                }

            }

        }

    }

    ll ans = INF;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {

            ans = min (ans, dp[(1 << N) - 1][i][k] + costs[k][i]);

        }
    }

    // cout << ans << endl;
    fout << ans << endl;


}


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

    solve(1);

    return 0;
}