#include <bits/stdc++.h>

// The below gets WA
// 


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 clear_dp(vector<vector<ll>> & dp, const int N, const int start_node_ID) {

    for (int i = 0; i < dp.size(); i++) {
        for (int j = 0; j < N; j++) {

            dp.at(i).at(j) = INF;

        }
    }

// dp.at(1 << start_node_ID).at(start_node_ID) = 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));

    ll ans = INF;

    // Start the simulation 
    // =======================
    for (int start_node_ID = 0; start_node_ID < N; start_node_ID++) {  // fix the ``i`` from previous implementation

        dp.at(1 << start_node_ID).at(start_node_ID) = 0LL;

        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]
                                                    );
                
                }

            }

        }
        // END for-loop over sets: ``S``


        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, start_node_ID);

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


    

    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;
}