#include <bits/stdc++.h>


using namespace std;


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


// #define INF 0x3f3f3f
// #define INF numeric_limits<int>::max()
#define INF pow(10, 8)
#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");
	ifstream fin("grader_test17.in");
    ofstream fout("hamilton.out");

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

    // ll costs[N][N];
    // int costs[N][N];
    vvi costs(N, vi (N, INF));

    // 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;
        costs.at(x).at(y) = c;
    }
    
    // bitmask dp
    // =====================
    // dp[1 << N][N] as shape, N = total no. of nodes
    
    // vector<vector<ll>> dp (1 << N, vll (N, INF));
    vvi dp(1 << N, vi (N, INF));

    // dim 0: subsets
    // dim 1: end_node_ID


    // BC's
    // =========
    int start_node_ID = 0; // because it actually doesn't matter where we start from
    dp.at(1 << start_node_ID).at(start_node_ID) = 0LL;
    
    // for (int i = 0; i < N; i++) {
    //     int S = 1 << i; // 2**i : the set which only contains node ``i``

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


    for (int S = 1; S < (1 << N); S++) {

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

            if ( 
                    (S & (1 << end_node_ID)) == 0 ||
                    (S & (1 << start_node_ID)) == 0
                ) 
            {
                continue;
            }

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

                if ( 
                        (costs.at(v).at(end_node_ID) == INF) || // if there isn't an edge between v and ``end_node_ID``
                        ((S & (1 << v)) == 0) // if v is not in 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]
                                                    dp.at(S ^ (1 << end_node_ID)).at(v) + costs.at(v).at(end_node_ID)
                                                );
                

            }
            // END for-loop over possible vertices ``v`` which can connect to ``end_node_ID``

        }
        // END for-loop over ``end_node_ID``

    }
    // END for-loop over sets S

    int ans = INF;
    // int ans = numeric_limits<int>::max();


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

        // if (costs[end_node_ID][0] != INF) {  // if it exists an edge between ``end_node_ID`` and node 0 (the start)
        if (costs.at(end_node_ID).at(0) != INF) {
            // fout << "BLA for end_node_ID = " << end_node_ID << endl;
            // fout << "For this bla we have: dp.at((1 << N) - 1).at(end_node_ID) = " << dp.at((1 << N) - 1).at(end_node_ID) << " and costs.at(end_node_ID).at(0) = " << costs.at(end_node_ID).at(0) << endl;
            // fout << "ans was = " << ans << endl;
            // ans = min(ans, dp.at((1 << N) - 1).at(end_node_ID) + costs[end_node_ID][0]);
            ans = min(
                          ans, 
                          dp.at((1 << N) - 1).at(end_node_ID) + costs.at(end_node_ID).at(0)
                     );
            // fout << "ans is now = " << ans << endl;

        }

    }

    if (ans != INF) {
    // if (ans != numeric_limits<int>::max()) {
        fout << ans << endl;
    }
    else {
        fout << "Nu exista solutie" << endl;
    }

}


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

    solve(1);

    return 0;
}