#include<bits/stdc++.h>

using namespace std;

const int inf = (1e9);

const int dim = (1e5);

char buff[dim + 5];

int pos = 0;

int cnt[7505];



void read(int &nr) { //functie de parsare
    int semn = 1;
    nr = 0;


    while (!isdigit(buff[pos])) {

        if (buff[pos] == '-') semn = -1;

        pos++;
        if (pos == dim) {
            pos = 0;
            fread(buff, 1, dim, stdin);
        }


    }


    while (isdigit(buff[pos])) {
        nr = nr * 10 + buff[pos] - '0';
        pos++;
        if (pos == dim) {
            pos = 0;
            fread(buff, 1, dim, stdin);
        }
    }

    nr *= semn;

}

bool cmp(pair<int, pair<int, int> > a,
         pair<int, pair<int, int> > b) { //criteriu de comparare pentru muchii (in esenta pentru Kruskal)
    if (a.second.second == b.second.second)
        return make_pair(a.first, a.second.first) < make_pair(b.first, b.second.first);

    return a.second.second < b.second.second;
}


class DSU { //clasa de DSU
private:
    int m_nodes;
    vector<int> t;
public:
    DSU(int n) {
        m_nodes = n;
        t.resize(n + 5);
        for (int i = 0; i <= n; i++)
            t[i] = -1;
    }

    inline int getRoot(int x) {
        int y = x;
        while (t[y] > 0) y = t[y];

        int root = y;

        y = x;

        while (y != root) {
            int aux = t[y];
            t[y] = root;
            y = aux;
        }

        return root;
    }

    inline void unite(int x, int y) {
        if (t[x] < t[y]) {
            t[x] += t[y];
            t[y] = x;
        } else {
            t[y] += t[x];
            t[x] = y;
        }
    }

};

class Graph {

private:

    int m_nodes;

    vector <vector<pair < int, int>> >
            m_adjList;//lista de adiacenta pentru fiecare nod sub forma {vecin,cost}


    vector <pair<int, pair < int, int>> >
            m_edges;//lista cu toate muchiile sub forma {nod1, {nod2, cost} }



    vector <vector<int>> c, f; //capacitatile si fluxurile

    bool m_areLabeled;
    //Ceva care sa retine daca e sau nu etichetat
    bool m_isDirected;
    //Ceva care sa retina daca e sau nu orientat

    struct tip { //Structura in care nodurile sunt ordonate dupa distanta (pentru Dijkstra)
        int nod;
        long long cost;

        bool operator<(const tip &other) const {
            return cost > other.cost;
        }
    };


    void topSort(vector<int> &solution, vector<bool> &seen, int node, int fat); //DFS pentru Sortare Topologica

    void
    tarjan(vector<bool> &inStack, vector<int> &st, vector<int> &lvl, vector<int> &low, vector <vector<int>> &solution,
           int node, int fat, int &currentLevel); //DFS pentru Tarjan

    void bicoDFS(vector<int> &t, vector <vector<int>> &solution, vector<int> &st, vector<bool> &seen, vector<int> &lvl,
                 vector<int> &low, int node, int fat, int currentLevel); //DFS pentru Biconexe

    void depthDFS(vector<int> &d, int node); //DFS de gasit adancimile (folosit la diametru)


    inline bool bfs(vector<int> &tt, int source, int destination); //BFS pentru flux




public:

    Graph(int nodes, bool areLabeled, bool isDirected = false,bool needFlow = false); //constructor

    void addCap(int from, int to, int cap); //adaugam o capacitate pe o muchie

    void addEdge(int from, int to, int cost = 0); //adaugam o muchie


    vector<long long> dijkstra(int source); //Dijkstra

    vector<int> bfs(int source); //BFS, returneaza distante

    void dfs(vector<bool> &m_visited, int node); //DFS, intoarce prin referinta vectorul de vizitati

    int getCC(); //Numarul de componente conexe


    vector <vector<int>> getSCCs(); //Componente tare conexe


    vector <vector<int>> getBiconected(); //Componente Biconexe

    vector <pair<int, int>> getCriticalEdges(); //Muchii critice

    vector<int> getTopSort(); //Sortare topologica

    static bool HavelHakimi(vector<int> degSequence); //Havel Hakimi, intoarce True/False


    pair<long long, vector<pair < int, int> > >

    getMST(); //APM cu Kruskal. Intoarce {cost,muchii}

    pair<int, vector<long long> > bellmanFord(int source); //Bellmanford, intoarce un errorcode si vectorul de distante

    vector <vector<int>> royFloyd(); //RoyFloyd. Intoarce matrice de distante

    vector<int> getDepths(int root); //getDepths. Calcul de adancimi

    int getTreeDiam(); //Diametrul unui arbore


    int getMaxFlow(int source, int destination); //Fluxul maxim

    pair<int, vector<int> > getEulerCycle(); //Pe prima pozitie avem 1 daca exista ciclu, altfel -1, iar pe a doua avem ciclul, daca exista, altfel un vector vid

    pair<int, vector<pair<int,int > > > getBipartiteMatching(int n,int m);

    int getPath(vector<int>&l, vector<int>&r, vector<bool>& seen,int node)
    {
        if(seen[node]) return 0;

        seen[node]=1;

        for(auto it:m_adjList[node])
        {
            if(!r[it.first])
            {
                l[node] =it.first;
                r[it.first] = node;
                return 1;
            }
        }

        for(auto it:m_adjList[node])
        {
            if(getPath(l,r,seen,r[it.first]))
            {
                l[node] = it.first;
                r[it.first] = node;
                return 1;
            }
        }
        return 0;

    }

    int getHamiltonCycleCost()
    {
        int lmask = (1<<m_nodes);

        vector<vector<int> > dp;

        dp.resize(lmask+5);

        for(int i=0;i<=lmask;i++) {
            dp[i].resize(m_nodes);
            fill(dp[i].begin(),dp[i].end(),inf);

        }

        dp[1][0] = 0;

        for(int mask=1;mask<lmask;mask++)
        {
            for(int j=0;j<m_nodes;j++)
            {

                if(dp[mask][j]==inf) continue;
                for(auto it:m_adjList[j+1])
                {
                    int nxt = it.first-1;
                    int cost = it.second;

                    if((1<<nxt) & mask) continue;

                    dp[mask | (1<<nxt)][nxt] = min(dp[mask | (1<<nxt)][nxt], dp[mask][j] + cost);
                }
            }
        }

        int sol=inf;

        vector<pair<int,int> > candidates;

        for(int i=1;i<=m_nodes;i++)
        {
            for(auto it:m_adjList[i])
                if(it.first == 1)
                {
                    candidates.push_back(make_pair(i,it.second));
                    break;
                }
        }
        for(auto it:candidates)
        {
            int nxt = it.first-1;
            int cost = it.second;

            sol = min(sol, dp[lmask-1][nxt] + cost);
        }

        return sol;

    }



};


pair<int, vector<pair<int,int> > > Graph::getBipartiteMatching(int n, int m)
{
    int augment=1;

    vector<bool> seen(m_nodes+5,false);

    vector<int> l(m_nodes+5,0);
    vector<int> r(m_nodes+5,0);


    while(augment)
    {
        augment=0;

        for(int i=1;i<=m_nodes;i++)
            seen[i] = false;

        for(int i=1;i<=n;i++)
            if(!l[i]) augment|=getPath(l,r,seen,i);

    }

    int matching =0;
    vector<pair<int,int> > solution;

    for(int i=1;i<=m_nodes;i++)
        if(l[i])
            solution.push_back(make_pair(i,l[i])),matching++;

    return make_pair(matching,solution);

}



void Graph::addCap(int from, int to, int cap) {
    c[from][to] = cap;
}

void Graph::topSort(vector<int> &solution, vector<bool> &seen, int node, int fat) {

    seen[node] = 1;

    for (auto it: m_adjList[node]) {
        if (seen[it.first]) continue;
        if (it.first == fat) continue;

        topSort(solution, seen, it.first, node);
    }

    solution.push_back(node);
}

void Graph::tarjan(vector<bool> &inStack, vector<int> &st, vector<int> &lvl, vector<int> &low,
                   vector <vector<int>> &solution,
                   int node, int fat, int &currentLevel) {
    low[node] = lvl[node] = ++currentLevel;
    st.push_back(node);

    inStack[node] = 1;

    for (auto it: m_adjList[node]) {
        if (!lvl[it.first]) {
            tarjan(inStack, st, lvl, low, solution, it.first, node, currentLevel);
            low[node] = min(low[node], low[it.first]);
        } else if (inStack[it.first]) {
            low[node] = min(low[node], low[it.first]);
        }
    }


    if (low[node] == lvl[node]) {
        solution.push_back({});
        int x = -1;

        while (x != node) {
            x = st.back();
            solution.back().push_back(x);
            inStack[x] = 0;
            st.pop_back();
        }
    }

}

void
Graph::bicoDFS(vector<int> &t, vector <vector<int>> &solution, vector<int> &st, vector<bool> &seen, vector<int> &lvl,
               vector<int> &low, int node, int fat, int currentLevel) {
    st.push_back(node);
    low[node] = lvl[node] = currentLevel;

    seen[node] = 1;


    for (auto it: m_adjList[node]) {
        if (it.first == fat) continue;

        if (seen[it.first]) {
            low[node] = min(low[node], lvl[it.first]);
            continue;
        }

        t[it.first] = node;
        bicoDFS(t, solution, st, seen, lvl, low, it.first, node, currentLevel + 1);

        low[node] = min(low[node], low[it.first]);

        if (low[it.first] >= lvl[node]) {
            solution.push_back({});
            int x = 0;

            do {
                x = st.back();
                solution.back().push_back(x);
                st.pop_back();
            } while (x != it.first);

            solution.back().push_back(node);
            // exit(0);
        }

    }
}

void Graph::depthDFS(vector<int> &d, int node) {
    for (auto it: m_adjList[node]) {
        if (d[it.first]) continue;
        d[it.first] = 1 + d[node];

        depthDFS(d, it.first);
    }
}

bool Graph::bfs(vector<int> &tt, int source, int destination) {
    vector<bool> seen(m_nodes + 5, false);
    deque<int> q;

    q.push_back(source);

    seen[source] = 1;

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

        q.pop_front();

        for (auto it: m_adjList[nod]) {
            if (!seen[it.first] && f[nod][it.first] < c[nod][it.first]) {
                tt[it.first] = nod;
                seen[it.first] = 1;
                q.push_back(it.first);
            }
        }
    }

    return seen[destination];
}

Graph::Graph(int nodes, bool areLabeled, bool isDirected,bool needFlow) {
    m_nodes = nodes;
    m_areLabeled = areLabeled;

    m_adjList.resize(nodes + 5);
    m_isDirected = isDirected;

    if(needFlow)
    {
        c.resize(m_nodes + 5);
        for (int i = 0; i <= m_nodes; i++)
            c[i].resize(m_nodes + 5);
        f.resize(m_nodes + 5);
        for (int i = 0; i <= m_nodes; i++)
            f[i].resize(m_nodes + 5);
    }
    //t.resize(nodes + 5);

    //for (int i = 0; i <= nodes; i++)
    //  t[i] = -1;
}

void Graph::addEdge(int from, int to, int cost) {
    m_adjList[from].push_back(make_pair(to, cost));
    if(m_isDirected || from<=to)
        m_edges.push_back(make_pair(from, make_pair(to, cost)));
}


vector<long long> Graph::dijkstra(int source) {

    priority_queue <tip> q;

    const long long inf = 10000000000LL;


    vector<long long> dp(m_nodes + 5, inf);

    dp[source] = 0;

    q.push({source, 0LL});

    while (!q.empty()) {
        int nod = q.top().nod;
        long long cost = q.top().cost;
        q.pop();

        if (cost > dp[nod]) continue;

        for (auto it: m_adjList[nod]) {
            long long z = cost + 1LL * it.second;
            if (z < dp[it.first]) {
                dp[it.first] = z;
                q.push({it.first, dp[it.first]});
            }
        }
    }

    return dp;
}

vector<int> Graph::bfs(int source) {
    deque<int> q;

    vector<int> distances(m_nodes + 5, -1);

    distances[source] = 0;

    q.push_back(source);


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

        q.pop_front();

        for (auto it: m_adjList[current]) {
            if (distances[it.first] == -1) {
                distances[it.first] = 1 + distances[current];
                q.push_back(it.first);
            }
        }

    }


    return distances;

}

void Graph::dfs(vector<bool> &m_visited, int node) {
    m_visited[node] = 1;

    for (auto it: m_adjList[node]) {
        if (m_visited[it.first]) continue;
        dfs(m_visited, it.first);
    }

}

bool Graph::HavelHakimi(vector<int> degSequence) {
    sort(degSequence.begin(), degSequence.end());
    reverse(degSequence.begin(), degSequence.end());

    int sz = (int) degSequence.size();

    for (int i = 0; i < sz; i++) {
        if (!degSequence[i]) break;
        for (int j = i + 1; j <= i + degSequence[i]; j++) {
            if (!degSequence[j]) return 0;
            if (j >= sz) return 0;

            degSequence[j]--;
        }


        int p = i + 1;
        int q = i + degSequence[i] + 1;

        vector<int> aux;
        while (p < i + degSequence[i] + 1 && q < sz) {
            if (degSequence[p] > degSequence[q])
                aux.push_back(degSequence[p]), p++;
            else
                aux.push_back(degSequence[q]), q++;
        }

        while (q < sz) aux.push_back(degSequence[q]), q++;
        while (p < i + degSequence[i] + 1) aux.push_back(degSequence[p]), p++;

        for (int j = i + 1; j < sz; j++)
            degSequence[j] = aux[j - i - 1];

        degSequence[i] = 0;
        //  for(auto it:degSequence)
        //     printf("%d ",it);
        // printf("\n");
    }


    return 1;
}

int Graph::getCC() {

    vector<bool> m_visited(m_nodes + 5, 0);


    int ans = 0;
    for (int i = 1; i <= m_nodes; i++)
        if (!m_visited[i]) dfs(m_visited, i), ans++;


    return ans;
}

vector <vector<int>> Graph::getSCCs() {
    vector <vector<int>> solution;
    vector<int> lvl(m_nodes + 5, 0);
    vector<int> low(m_nodes + 5, 0);
    vector<int> st;
    vector<bool> inStack(m_nodes + 5, 0);
    int currentLevel = 0;

    for (int i = 1; i <= m_nodes; i++)
        if (!lvl[i])
            tarjan(inStack, st, lvl, low, solution, i, 0, currentLevel);

    return solution;
}

vector <vector<int>> Graph::getBiconected() {
    vector <vector<int>> solution;
    vector<int> lvl(m_nodes + 5, 0);
    vector<int> low(m_nodes + 5, 0);
    vector<int> st;
    vector<bool> seen(m_nodes + 5, 0);
    vector<int> t(m_nodes + 5, 0);

    bicoDFS(t, solution, st, seen, lvl, low, 1, 0, 1);

    return solution;

}

vector <pair<int, int>> Graph::getCriticalEdges() {
    vector <vector<int>> solution;
    vector<int> lvl(m_nodes + 5, 0);
    vector<int> low(m_nodes + 5, 0);
    vector<int> st;
    vector<bool> seen(m_nodes + 5, 0);
    vector<int> t(m_nodes + 5, 0);

    bicoDFS(t, solution, st, seen, lvl, low, 1, 0, 1);

    vector <pair<int, int>> criticals;
    for (auto it: m_edges) {
        int x = it.first;
        int y = it.second.first;

        if (x == y) continue;

        if (lvl[x] < lvl[y]) continue;

        if (t[x] == y && low[x] > lvl[y])
            criticals.push_back(make_pair(x, y));
    }


    return criticals;
}

vector<int> Graph::getTopSort() {
    vector<int> solution;
    vector<bool> seen(m_nodes + 5, 0);

    for (int i = 1; i <= m_nodes; i++)
        if (!seen[i])
            topSort(solution, seen, i, 0);

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

    return solution;
}

pair<long long, vector<pair < int, int> > >

Graph::getMST() {
    sort(m_edges.begin(), m_edges.end(), cmp);
    vector <pair<int, int>> sol;

    DSU disjointSet(m_nodes);


    long long cost = 0;

    for (auto it: m_edges) {
        int x = it.first;
        int y = it.second.first;
        int z = it.second.second;

        int rx = disjointSet.getRoot(x);
        int ry = disjointSet.getRoot(y);

        if (rx != ry) {
            cost += 1LL * z;
            disjointSet.unite(rx, ry);
            sol.push_back(make_pair(x, y));
        }
    }


    return make_pair(cost, sol);

}

pair<int, vector<long long> > Graph::bellmanFord(int source) {
    deque<int> q;

    vector<bool> inQueue(m_nodes + 5, 0);
    vector<int> seen(m_nodes + 5, 0);


    q.push_back(source);
    inQueue[source] = seen[source] = 1;

    vector<long long> dp(m_nodes + 5, 1LL * INT_MAX);

    dp[source] = 0;

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

        for (auto it: m_adjList[node]) {
            if (dp[it.first] < dp[node] + it.second) continue;

            dp[it.first] = dp[node] + it.second;
            if (!inQueue[it.first]) {
                q.push_back(it.first);
                inQueue[it.first] = 1;
            }

            seen[it.first]++;
            if (seen[it.first] == (m_nodes + 1))
                return make_pair(-1, dp);
        }

        inQueue[node] = 0;
        q.pop_front();
    }

    return make_pair(0, dp);


}

vector <vector<int>> Graph::royFloyd() {
    vector <vector<int>> m;

    m.resize(m_nodes + 5);
    for (int i = 0; i <= m_nodes; i++)
        m[i].resize(m_nodes + 5);

    for (auto it: m_edges) {
        int x = it.first;
        int y = it.second.first;
        m[x][y] = it.second.second;
    }

    for (int i = 1; i <= m_nodes; i++) {
        for (int j = 1; j <= m_nodes; j++) {
            if (i == j) continue;
            if (!m[i][j]) m[i][j] = inf;
        }
    }

    for (int k = 1; k <= m_nodes; k++) {
        for (int i = 1; i <= m_nodes; i++)
            for (int j = 1; j <= m_nodes; j++) {
                if (m[i][k] + m[k][j] < m[i][j]) m[i][j] = m[i][k] + m[k][j];
            }
    }

    return m;
}

vector<int> Graph::getDepths(int root) {
    vector<int> depths(m_nodes + 5, 0);
    depths[root] = 1;

    depthDFS(depths, root);


    return depths;

}

int Graph::getTreeDiam() {
    vector<int> depth = getDepths(1);

    int best = 1;
    for (int i = 1; i <= m_nodes; i++)
        if (depth[i] > depth[best]) best = i;

    depth = getDepths(best);

    for (int i = 1; i <= m_nodes; i++)
        if (depth[i] > depth[best]) best = i;

    return depth[best];
}

int Graph::getMaxFlow(int source, int destination) {

    vector<int> tt;


    tt.resize(m_nodes + 5);

    int sol = 0;

    while (bfs(tt, source, destination)) {

        for (auto it: m_adjList[destination]) {
            int x = it.first;
            int flow = c[x][destination] - f[x][destination];

            for (int i = x; i != source; i = tt[i])
                flow = min(flow, c[tt[i]][i] - f[tt[i]][i]);

            f[x][destination] += flow;
            f[destination][x] -= flow;

            for (int i = x; i != source; i = tt[i]) {
                f[tt[i]][i] += flow;
                f[i][tt[i]] -= flow;
            }

            sol += flow;
        }
    }

    return sol;
}

pair<int, vector<int> > Graph::getEulerCycle()
{
    vector<int> aux;

    for(int i=1;i<=m_nodes;i++)
        if((int)m_adjList[i].size()%2) return make_pair(-1,aux);



  //  for(int i=1;i<=m_nodes;i++)
    //    sort(m_adjList[i].begin(),m_adjList[i].end());

    vector<int> solution;
    int m= (int)m_edges.size();
    int *st;
    int vf=0;
    //cerr<<m<<'\n';


    st = new int[m+5];

    vector<bool> seen(m+5,false);
   // exit(0);

    st[++vf] = 1;


    while(vf)
    {
        int node = st[vf];
        //vf--;

        while(!m_adjList[node].empty() && seen[m_adjList[node].back().second]) m_adjList[node].pop_back();
        if(m_adjList[node].empty()) {
            solution.push_back(node);
            vf--;
            continue;

        }
        pair<int,int> adj = m_adjList[node].back();
        seen[m_adjList[node].back().second] =1;
       // m_adjList[adj.first].erase( lower_bound(m_adjList[adj.first].begin(),m_adjList[adj.first].end(),make_pair(node,adj.second)));
        st[++vf] = adj.first;

    }
    delete[] st;

    return make_pair(1,solution);


}


int main() {

    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    int n, m, x, y, z;

    scanf("%d%d", &n, &m);

    Graph G(n, 1, 1,0);


    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y,&z);

        x++;
        y++;

        G.addEdge(x, y,z);

    }

    int sol = G.getHamiltonCycleCost();

    printf("%d\n",sol);


    return 0;



}