/*
Alexandru Enache
Grupa 252
*/

#include <bits/stdc++.h>
using namespace std;

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


const int inf = 1e9;

class Graph{

private:

    int m_nodes;
    vector < vector < int > > m_gr;
    vector < vector < pair < int, int > > > m_weighted_gr;
    vector < pair < int, pair < int , int > > > m_weighted_edges;
    vector < int > m_disjointParent, m_disjointCardinal;
    vector < vector < int > > m_capacity;
    vector < pair < pair <int , int > , bool> > m_edges;


    void dfs(int node, vector < bool > &used){
        used[node] = true;
        for (auto &x: m_gr[node]){
            if (!used[x]){
                dfs(x, used);
            }
        }
    }

    void dfs_biconexe (int nod , int dad, vector < int > &lv, vector < int > &MIN, stack < int > &s, vector < vector < int > > &ans){
        lv[nod] = lv[dad]+1;
        MIN[nod] = lv[nod];
        s.push(nod);
        for (auto &x : m_gr[nod]){
            if (lv[x]){
                if (x != dad){
                    MIN[nod] = min(MIN[nod] , lv[x]);
                }
            }
            else{
                dfs_biconexe(x , nod, lv, MIN, s, ans);
                MIN[nod] = min(MIN[nod] , MIN[x]);
                if (MIN[x] >= lv[nod]){
                    vector < int > aux;
                    while (s.top() != x){
                        aux.push_back(s.top());
                        s.pop();
                    }
                    aux.push_back(x);
                    s.pop();
                    aux.push_back(nod);
                    ans.push_back(aux);
                }
            }
        }
    }

    void dfs_ctc(int nod, vector < vector < int > > &gr, vector < bool > &used, vector < int > &aux){
        used[nod] = true;
        for (auto& x : gr[nod]) {
            if (!used[x]) {
                dfs_ctc(x, gr, used, aux);
            }
        }
        aux.push_back(nod);
    }

    void dfs_lv(int node, vector < int > &lv){
        for (auto &x: m_gr[node]){
            if (!lv[x]){
                lv[x] = lv[node] + 1;
                dfs_lv(x, lv);
            }
        }
    }

    bool bfs_max_flow(int source, int destination, vector < int > &dad, vector < vector < int > > &flow){
        for (int i = 1; i <= m_nodes; i++) {
            dad[i] = 0;
        }
        dad[source] = source;

        queue < int > q;
        q.push(source);
        int ok = 0;

        while (!q.empty()) {
            int now = q.front();
            q.pop();
            if (now == destination) {
                ok = 1;
                continue;
            }
            for (auto& x : m_gr[now]) {
                if (!dad[x] && m_capacity[now][x] - flow[now][x] > 0) {
                    dad[x] = now;
                    q.push(x);
                }
            }
        }
        return ok;
    }

    int euler_nxt(int nod , pair < pair < int , int > , bool> &edg){
        edg.second = true;
        if (edg.first.first == nod){
            return edg.first.second;
        }
        return edg.first.first;
    }


public:

    Graph(){
        m_nodes = 0;
        m_gr = {};
    }

    Graph(int nodes, vector < vector < int > > &gr){
        m_nodes = nodes;
        m_gr = gr;

        m_disjointParent.resize(nodes+1);
        m_disjointCardinal.resize(nodes+1);

        for (int i=1; i<=nodes; i++) {
            m_disjointParent[i] = i;
            m_disjointCardinal[i] = 1;
        }
    }

    Graph(int nodes, vector < vector < pair < int , int > > > &weighted_gr){
        m_nodes = nodes;
        m_weighted_gr = weighted_gr;

        m_disjointParent.resize(nodes+1);
        m_disjointCardinal.resize(nodes+1);

        for (int i=1; i<=nodes; i++) {
            m_disjointParent[i] = i;
            m_disjointCardinal[i] = 1;
        }
    }

    Graph(int nodes, vector < pair < int, pair < int , int >  > > &weighted_edges){
        m_nodes = nodes;
        m_weighted_edges = weighted_edges;

        m_disjointParent.resize(nodes+1);
        m_disjointCardinal.resize(nodes+1);

        for (int i=1; i<=nodes; i++) {
            m_disjointParent[i] = i;
            m_disjointCardinal[i] = 1;
        }
    }

    Graph(int nodes, vector < vector < int > > &gr, vector < vector < int > > &capacity){
        m_nodes = nodes;
        m_gr = gr;
        m_capacity = capacity;
    }

    Graph(int nodes, vector < vector < int > > &gr, vector < pair < pair <int , int > , bool> > edges){
        m_nodes = nodes;
        m_gr = gr;
        m_edges = edges;
    }

    vector < int > bfs(int start){
        queue < int > q;
        vector < int > dist(m_nodes + 1, -1);

        dist[start] = 0;
        q.push(start);

        while (!q.empty()){
            int now = q.front();
            q.pop();

            for (auto &x : m_gr[now]){
                if (dist[x] == -1){
                    dist[x] = dist[now] + 1;
                    q.push(x);
                }
            }
        }

        return dist;
    }

    int comp_conexe(){

        int cont = 0;
        vector < bool > used(m_nodes + 1, false);
        for (int i=1; i<=m_nodes; i++){
            if (!used[i]){
                dfs(i, used);
                cont++;
            }
        }

        return cont;
    }

    vector < vector < int > > comp_biconexe(){

        vector < vector < int > > ans;

        vector < int > lv (m_nodes + 1, 0);
        vector < int > MIN (m_nodes + 1, 0);
        stack < int > s;

        for (int i=1; i<=m_nodes; i++){
            if (!lv[i]){
                dfs_biconexe(i , 0, lv, MIN, s, ans);
                while (!s.empty()) s.pop();
            }
        }

        return ans;
    }

    vector < vector < int > > ctc(){

        vector < vector < int > > ans;

        vector < bool > used(m_nodes + 1, false);
        vector < int > ord;

        for (int i=1; i<=m_nodes; i++) if (!used[i]) dfs_ctc(i, m_gr, used, ord);

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

        vector < vector < int > > inv(m_nodes + 1);

        for (int i=1; i<=m_nodes; i++){
            used[i] = false;
            for (auto &x : m_gr[i]){
                inv[x].push_back(i);
            }
        }

        for (auto &x: ord){
            if (!used[x]){
                vector < int > aux;
                dfs_ctc(x, inv, used, aux);
                ans.push_back(aux);
            }
        }

        return ans;
    }

    vector < int > ord_topologica(){

        vector < bool > used(m_nodes + 1, false);
        vector < int > ord;

        for (int i=1; i<=m_nodes; i++) if (!used[i]) dfs_ctc(i, m_gr, used, ord);

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

        return ord;
    }

    bool Havel_Hakimi(vector < int > v){

        for (int i=0; i<v.size(); i++){
            sort(v.begin(), v.end());
            reverse(v.begin(), v.end());

            if (v[0] > (int)v.size()-1) return false;

            for (int j=1; j<=v[0]; j++){
                v[j]--;
                if (v[j] < 0) return false;
            }
            v[0] = 0;
        }

        return true;
    }

    //disjoint
    int disjoint_find_parent(int node){
        if (node != m_disjointParent[node]) {
            m_disjointParent[node] = disjoint_find_parent(m_disjointParent[node]);
        }
        return m_disjointParent[node];
    }

    void disjoint_unite(int node_A, int node_B) {
        node_A = disjoint_find_parent(node_A);
        node_B = disjoint_find_parent(node_B);
        if (m_disjointCardinal[m_disjointParent[node_A]] > m_disjointCardinal[m_disjointParent[node_B]]) {
            int old_value = m_disjointCardinal[m_disjointParent[node_B]];
            m_disjointParent[node_B] = m_disjointParent[node_A];
            m_disjointCardinal[m_disjointParent[node_A]] += old_value;
        }
        else {
            int old_value = m_disjointCardinal[m_disjointParent[node_A]];
            m_disjointParent[node_A] = m_disjointParent[node_B];
            m_disjointCardinal[m_disjointParent[node_B]] += old_value;
        }
    }

    //minimum spanning tree
    vector < pair <int , pair < int , int > > > minimum_spanning_tree(){
        vector < pair <int , pair < int , int > > > answer;

        sort(m_weighted_edges.begin(), m_weighted_edges.end());

        for (auto &x : m_weighted_edges){
            if (disjoint_find_parent(x.second.first) != disjoint_find_parent(x.second.second)){
                answer.push_back(x);
                disjoint_unite(x.second.first, x.second.second);
            }
        }

        return answer;
    }

    //dijkstra
    vector < int > dijkstra (int source){
        vector < int > dp(m_nodes + 1, inf);

        priority_queue<pair<int,int> , vector<pair<int , int>> , greater<>> Q;
        vector < bool > used(m_nodes + 1, false);

        dp[source] = 0;
        Q.push({0 , source});

        while (!Q.empty()){
            pair<int , int> now = Q.top();
            Q.pop();
            if (used[now.second] || now.first != dp[now.second]){
                continue;
            }
            used[now.second] = true;
            for (auto &x : m_weighted_gr[now.second]){
                if (dp[x.first] > now.first + x.second){
                    dp[x.first] = now.first + x.second;
                    Q.push({dp[x.first], x.first});
                }
            }
        }

        return dp;
    }

    //belman-ford
    vector < int > bellman_ford(int source){
        vector < int > dp(m_nodes + 1, inf);

        queue <int> Q;
        vector < bool > used(m_nodes + 1, false);
        vector < int > fv(m_nodes + 1, 0);

        dp[source] = 0;
        Q.push(source);

        while (!Q.empty()){

            int now = Q.front();
            Q.pop();
            fv[now]++;
            used[now] = false;

            if (fv[now] > m_nodes){
                return {};
            }

            for (auto &x : m_weighted_gr[now]){
                if (dp[x.first] > dp[now] + x.second){
                    dp[x.first] = dp[now] + x.second;
                    if (!used[x.first]){
                        Q.push(x.first);
                        used[x.first] = true;
                    }
                    else{
                        fv[x.first]++;
                    }
                }
            }

        }


        return dp;
    }

    int diametru_arbore(){
        vector < int > lv (m_nodes+1, 0);
        lv[1] = 1;
        dfs_lv(1, lv);

        int MAX = 0;
        int pos = 0;
        for (int i=1; i<=m_nodes; i++){
            if (MAX < lv[i]){
                MAX = lv[i];
                pos = i;
            }
        }

        for(auto &x : lv){
            x = 0;
        }
        lv[pos] = 1;
        dfs_lv(pos, lv);

        MAX = 0;
        for (int i=1; i<=m_nodes; i++){
            MAX = max(MAX, lv[i]);
        }

        return MAX;
    }

    vector < vector < int > > RoyFloyd(){
        for (int k=1; k<=m_nodes; k++){
            for (int i=1; i<=m_nodes; i++){
                if (k == i || m_gr[i][k] == inf){
                    continue;
                }
                for (int j=1; j<=m_nodes; j++){
                    if (i == j || m_gr[k][j] == inf){
                        continue;
                    }
                    m_gr[i][j] = min (m_gr[i][j] , m_gr[i][k] + m_gr[k][j]);
                }
            }
        }
        return m_gr;
    }

    int max_flow(int source, int destination){
        int ans = 0;

        vector < int > dad(m_nodes + 1, 0);
        vector < vector < int > > flow (m_nodes + 1);
        for (auto &x: flow){
            x.resize(m_nodes + 1, 0);
        }

        while (bfs_max_flow(source, destination, dad, flow)) {
            for (auto& x : m_gr[destination]) {
                if (!dad[x]) {
                    continue;
                }
                dad[destination] = x;
                int now = destination;
                int MIN = inf;
                while (now != source) {
                    MIN = min(MIN, m_capacity[dad[now]][now] - flow[dad[now]][now]);
                    now = dad[now];
                }
                now = destination;
                while (now != source) {
                    flow[dad[now]][now] += MIN;
                    flow[now][dad[now]] -= MIN;
                    now = dad[now];
                }
                ans += MIN;
            }
        }

        return ans;
    }

    vector < int > ciclu_euler(){

        vector < int > poz(m_nodes + 1, -1);
        vector < int > ans;

        for (int i=1; i<=m_nodes; i++){
            if (m_gr[i].size() % 2){
                return ans;
            }
        }

        stack < int > s;

        s.push(1);

        while (!s.empty()){
            int nod = s.top();
            //cout<<nod<<'\n';
            int ok = 1;
            while (poz[nod] + 1 < (int)m_gr[nod].size()){
                poz[nod]++;
                if (!m_edges[m_gr[nod][poz[nod]]].second){
                    s.push(euler_nxt(nod , m_edges[m_gr[nod][poz[nod]]]));
                    ok = 0;
                    break;
                }
            }
            if (ok){
                s.pop();
                ans.push_back(nod);
            }
        }

        ans.pop_back();

        if (ans.size() != m_edges.size()){
            ans.clear();
        }

        return ans;

    }

    int ciclu_hamilton_cost_minim(){

        vector < vector <int> > mask (m_nodes + 1 );
        vector < vector < int > > dp ((1 << m_nodes));

        for (auto &x : dp){
            x.resize(m_nodes + 1 , 0);
        }

        for (int masc=0; masc<(1 << m_nodes); masc++){
            int cont = 0;
            for (int bit = 0; bit < m_nodes; bit++){
                if (masc & (1 << bit)){
                    cont ++;
                }
            }
            mask[cont].push_back(masc);
        }

        for (int i=1; i<=m_nodes; i++){
            for (auto &x : mask[i]){
                for (int l=0; l<m_nodes; l++){
                    if (dp[x][l] != 0 || (x == 1 && l == 0)){
                        for (int bit = 0; bit<m_nodes; bit++){
                            if ((!(x & (1 << bit))) && m_gr[l][bit] != 0){
                                if (dp[x + (1 << bit)][bit] == 0){
                                    dp[x + (1 << bit)][bit] = dp[x][l] + m_gr[l][bit];
                                }
                                else{
                                    dp[x + (1 << bit)][bit] = min(dp[x + (1 << bit)][bit] , dp[x][l] + m_gr[l][bit]);
                                }
                            }
                        }
                    }
                }
            }
        }

        int MIN = inf;
        for (int l=0; l<m_nodes; l++){
            if (dp[(1 << m_nodes) - 1][l] != 0 && m_gr[l][0] != 0){
                MIN = min(MIN , dp[(1 << m_nodes) - 1][l] + m_gr[l][0]);
            }
        }

        return MIN;
    }

};


void solve() {

    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    fin >> n >> m;

    vector < vector < int > > gr (n+1);
    for (auto &x: gr){
        x.resize(n+1, 0);
    }

    while (m--){
        int node_A, node_B, cost;
        fin >> node_A >> node_B >> cost;
        gr[node_A][node_B] = cost;
    }

    Graph graph = Graph(n, gr);

    int ans = graph.ciclu_hamilton_cost_minim();

    if (ans == inf){
        fout<<"Nu exista solutie";
        return;
    }

    fout<<ans;

}


int main() {

    solve();

    return 0;
}