#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
#include<algorithm>
#include<set>
using namespace std;

struct muchieCost {
    int x, y, cost;
    bool operator< (muchieCost other) {
        return cost < other.cost;
    }
};

struct muchieCapacitate {
    int x, y, capacitate;
};

class DisjointSet {
    int n;
    vector<int> r;
public:
    DisjointSet(int n);
    void merge(int x, int y);
    bool find(int x, int y);
private:
    int root(int x);
    void mergeRoot(int x, int y);
};

DisjointSet::DisjointSet(int n) {
    this->n = n;
    r.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        r[i] = -1;
    }
}

void DisjointSet :: merge(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    if (rootx != rooty) {
        if (r[rootx] < r[rooty]) {
            mergeRoot(rootx, rooty);
        }
        else {
            mergeRoot(rooty, rootx);
        }
    }
}

bool DisjointSet::find(int x, int y) {
    return root(x) == root(y);
}

int DisjointSet::root(int x) {
    while (r[x] > 0) {
        x = r[x];
    }
    return x;
}

void DisjointSet :: mergeRoot(int x, int y) {
    r[x] += r[y];
    r[y] = x;
}


class Graf {
    int n;
    int m;
    vector< vector<int> > vecini;
    vector< vector< pair<int, int> > > veciniCost;
    vector<muchieCost> muchiiCost;
    vector<muchieCapacitate> muchiiCapacitate;
    vector< vector<int> > adiacenta;
 public:
    Graf(int n);
    Graf(int n, int m, pair<int, int> muchii[], bool directed);
    Graf(int n, vector< vector<int> > muchii, bool directed);
    Graf(int n, int m, muchieCost muchii[], bool directed);
    Graf(int n, vector< vector<int> > adiacenta);
    Graf(int n, int m, muchieCapacitate muchii[]);
    void adaugaMuchie(int x, int y, bool orientata);
    int nrComponenteConexe();
    vector<int> bfs(int srs);
    vector<int> sortareTopologica();
    vector< vector<int> > componenteTareConexe();
    vector< vector<int> > componenteBiconexe();
    vector< vector<int> > muchiiCritice();
    int arborePartialMinim(vector< pair<int, int> > &muchiiArbore);
    vector<int> dijkstra(int sursa);
    bool bellmanFord(int sursa, vector<int> &distanta);
    int diametruArbore();
    vector< vector<int> > royFloyd();
    int fluxMaxim(const int sursa, const int destinatie);
    vector<int> cicluEulerian();
    int costCicluHamiltonian();
private:
    void dfs(int nod, vector<bool> &viz);
    void dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz);
    void dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s, vector<bool> &inStack,
                       vector< vector<int> > &componente, int &cnt, vector<bool> &viz);
    void dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &viz);
    bool bfsFlux(const int sursa, const int destinatie, vector< vector<int> > &flux, vector< vector<int> > &capacitate,
                 vector<int> &tata, vector<bool> &vizitat);
};

Graf :: Graf(int n) {
    vecini.resize(n + 1);
    this->n = n;
    this->m = 0;
}

Graf :: Graf(int n, int m, pair<int, int> muchii[], bool directed) {
    this->n = n;
    this->m = m;
    vecini.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        vecini[ muchii[i].first ].push_back(muchii[i].second);
        if (!directed) {
            vecini[ muchii[i].second ].push_back(muchii[i].first);
        }
    }
}

Graf :: Graf(int n, vector< vector<int> > muchii, bool directed) {
    this->n = n;
    this->m = muchii.size();
    vecini.resize(n + 1);
    for (int i = 0; i < muchii.size(); i++) {
        vecini[ muchii[i][0] ].push_back(muchii[i][1]);
        if (!directed) {
            vecini[ muchii[i][1] ].push_back(muchii[i][0]);
        }
    }
}

Graf :: Graf(int n, int m, muchieCost muchii[], bool directed) {
    this->n = n;
    this->m = m;
    veciniCost.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        veciniCost[ muchii[i].x ].push_back(make_pair(muchii[i].y, muchii[i].cost));
        if (!directed) {
            veciniCost[ muchii[i].y ].push_back(make_pair(muchii[i].x, muchii[i].cost));
            muchiiCost.push_back(muchii[i]);
        }
    }
}

Graf :: Graf(int n, int m, muchieCapacitate muchii[]) {
    this->n = n;
    this->m = m;
    vecini.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        muchiiCapacitate.push_back(muchii[i]);
        vecini[ muchii[i].x ].push_back(muchii[i].y);
        vecini[ muchii[i].y ].push_back(muchii[i].x);
    }
}

Graf :: Graf (int n, vector< vector<int> > adiacenta) {
    this->n = n;
    this->adiacenta.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        this->adiacenta[i].resize(n + 1);
        for (int j = 1; j <= n; j++) {
            this->adiacenta[i][j] = adiacenta[i][j];
        }
    }
}

void Graf :: adaugaMuchie(int x, int y, bool orientata) {
    vecini[x].push_back(y);
    if (!orientata) {
        vecini[y].push_back(x);
    }
}

int Graf :: nrComponenteConexe() {
    vector<bool> viz;
    viz.resize(n + 1);
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i, viz);
        }
    }
    return nr;
}
void Graf :: dfs(int nod, vector<bool> &viz) {
    viz[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        if (!viz[ vecini[nod][i] ]) {
            dfs(vecini[nod][i], viz);
        }
    }
}
vector<int> Graf :: bfs(int srs) {
    vector<int> dist;
    dist.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    queue<int> q;
    q.push(srs);
    dist[srs] = 0;
    while (!q.empty()) {
        int nod = q.front();
        for (int i = 0; i < vecini[nod].size(); i++) {
            int vecin = vecini[nod][i];
            if (dist[vecin] == -1) {
                dist[vecin] = dist[nod] + 1;
                q.push(vecin);
            }
        }
        q.pop();
    }
    return dist;
}

vector<int> Graf :: sortareTopologica() {
    vector<int> noduriSortate;
    vector<bool> viz;
    viz.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsSortare(i, noduriSortate, viz);
        }
    }
    for (int i = 0; i < n / 2; i++) {
        swap(noduriSortate[i], noduriSortate[n - i - 1]);
    }
    return noduriSortate;
}

void Graf :: dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz) {
    viz[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!viz[vecin]) {
            dfsSortare(vecin, noduriSortate, viz);
        }
    }
    noduriSortate.push_back(nod);
}

vector< vector<int> > Graf :: componenteTareConexe() {
    vector<int> level, low;
    vector<bool> inStack, viz;
    level.resize(n + 1);
    low.resize(n + 1);
    inStack.resize(n + 1);
    viz.resize(n + 1);
    int cnt = 0;
    vector< vector<int> > componente;
    stack<int> s;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsTareConexe(i, level, low, s, inStack, componente, cnt, viz);
        }
    }
    return componente;
}

void Graf :: dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s,
                vector<bool> &inStack, vector< vector<int> > &componente, int &cnt, vector<bool> &viz) {

    viz[nod] = true;
    cnt++;
    level[nod] = low[nod] = cnt;
    s.push(nod);
    inStack[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!viz[vecin]) {
            dfsTareConexe(vecin, level, low, s, inStack, componente, cnt, viz);
        }
        if (inStack[vecin]) {
            low[nod] = min(low[nod], low[vecin]);
        }
    }
    if (low[nod] == level[nod]) {
        vector<int> noduriComponenta;
        int nodComponenta;
        do {
            nodComponenta = s.top();
            inStack[nodComponenta] = 0;
            s.pop();
            noduriComponenta.push_back(nodComponenta);
        } while (nodComponenta != nod);
        componente.push_back(noduriComponenta);
    }
}

vector< vector<int> > Graf :: componenteBiconexe() {
    vector<int> level, low;
    vector<bool>  viz;
    level.resize(n + 1);
    low.resize(n + 1);
    viz.resize(n + 1);
    vector< vector<int> > componente;
    stack<int> s;
    dfsBiconexe(1, 0, level, low, s, componente, viz);
    return componente;
}

vector< vector<int> > Graf :: muchiiCritice() {
    vector<int> level, low;
    vector<bool>  viz;
    level.resize(n + 1);
    low.resize(n + 1);
    viz.resize(n + 1);
    vector< vector<int> > componente, critice;
    stack<int> s;
    dfsBiconexe(1, 0, level, low, s, componente, viz);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < vecini[i].size(); j++) {
            if (low[ vecini[i][j] ] > level[i]) {
                vector<int> muchie;
                muchie.push_back(i);
                muchie.push_back(vecini[i][j]);
                critice.push_back(muchie);
            }
        }
    }
    return critice;
}

void Graf:: dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &viz) {

    viz[nod] = 1;
    level[nod] = low[nod] = level[tata] + 1;
    s.push(nod);
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (vecin == tata) {
            continue;
        }
        if (viz[vecin] == 1) {
            low[nod] = min(low[nod], level[vecin]);
            continue;
        }
        dfsBiconexe(vecin, nod, level, low, s, componente, viz);
        low[nod] = min(low[nod], low[vecin]);
        if (low[vecin] >= level[nod]) {
            vector<int> componenta;
            componenta.push_back(nod);
            int nodComponenta;
            do{
                nodComponenta = s.top();
                componenta.push_back(nodComponenta);
                s.pop();
            } while (nodComponenta != vecin);
            componente.push_back(componenta);
        }
    }
}

int Graf :: arborePartialMinim(vector< pair<int, int> > &muchiiArbore) {
    sort(muchiiCost.begin(), muchiiCost.end());
    int suma = 0;
    DisjointSet *disjointSet = new DisjointSet(n);
    for (int i = 0; i < muchiiCost.size(); i++) {
        if (!disjointSet->find(muchiiCost[i].x, muchiiCost[i].y)) {
            disjointSet->merge(muchiiCost[i].x, muchiiCost[i].y);
            suma += muchiiCost[i].cost;
            muchiiArbore.push_back(make_pair(muchiiCost[i].x, muchiiCost[i].y));
        }
    }
    return suma;
}

vector<int> Graf :: dijkstra(int sursa) {
    vector<int> distanta;
    distanta.resize(n + 1);
    vector<bool> vizitat;
    vizitat.resize(n + 1);
    set< pair<int, int> > h;
    const int inf = 2000000000;
    for (int i = 1; i <= n; i++) {
        distanta[i] = inf;
        if (i == sursa) {
            distanta[i] = 0;
        }
        h.insert(make_pair(distanta[i], i));
    }
    while (!h.empty() && h.begin()->first != inf) {
        int nod = h.begin()->second;
        h.erase(h.begin());
        vizitat[nod] = true;
        for (int i = 0; i < veciniCost[nod].size(); i++) {
            int vecin = veciniCost[nod][i].first;
            if (!vizitat[vecin] && distanta[vecin] > distanta[nod] + veciniCost[nod][i].second) {
                h.erase(make_pair(distanta[vecin], vecin));
                distanta[vecin] = distanta[nod] + veciniCost[nod][i].second;
                h.insert(make_pair(distanta[vecin], vecin));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (distanta[i] == inf) {
            distanta[i] = 0;
        }
    }
    return distanta;
}

bool Graf :: bellmanFord(int sursa, vector<int> &distanta) {
    vector<int> nrVizitat;
    queue<int> coada;
    vector<bool> inCoada;
    distanta.resize(n + 1);
    nrVizitat.resize(n + 1);
    inCoada.resize(n + 1);
    const int inf = 2000000000;
    for (int i = 1; i <= n; i++) {
        distanta[i] = inf;
    }
    distanta[sursa] = 0;
    inCoada[sursa] = true;
    coada.push(sursa);
    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        inCoada[nod] = false;
        nrVizitat[nod] ++;
        if (nrVizitat[nod] == n) {
            return true;
        }
        for (int i = 0; i < veciniCost[nod].size(); i++) {
            int vecin = veciniCost[nod][i].first;
            if (distanta[vecin] > distanta[nod] + veciniCost[nod][i].second) {
                distanta[vecin] = distanta[nod] + veciniCost[nod][i].second;
                if (!inCoada[vecin]) {
                    inCoada[vecin] = true;
                    coada.push(vecin);
                }
            }
        }
    }
    return false;
}

int Graf :: diametruArbore() {
    vector<int> distanta = bfs(1);
    int nodDepartat = 1;
    for (int i = 2; i <= n; i++) {
        if (distanta[i] > distanta[nodDepartat]) {
            nodDepartat = i;
        }
    }
    distanta = bfs(nodDepartat);
    int diametru = 0;
    for (int i = 1; i <= n; i++) {
        diametru = max(diametru, distanta[i]);
    }
    return diametru + 1;
}

vector< vector<int> > Graf :: royFloyd() {
    vector< vector<int> > distanta(n + 1);
    for (int i = 1; i <= n; i++) {
        distanta[i].resize(n + 1);
        for (int j = 1; j <= n; j++) {
            distanta[i][j] = adiacenta[i][j];
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i != k && j != k && i != j && distanta[i][k] != 0 && distanta[k][j] != 0 &&
                   (distanta[i][k] + distanta[k][j] < distanta[i][j] || distanta[i][j] == 0)){
                    distanta[i][j] = distanta[i][k] + distanta[k][j];
                }
            }
        }
    }
    return distanta;
}

bool Graf :: bfsFlux(const int sursa, const int destinatie, vector< vector<int> > &flux, vector< vector<int> > &capacitate,
             vector<int> &tata, vector<bool> &vizitat) {
    queue<int> coada;
    vizitat.resize(n + 1);
    tata.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        vizitat[i] = false;
    }
    vizitat[sursa] = true;
    coada.push(sursa);
    tata[sursa] = 0;
    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        for(int i = 0; i < vecini[nod].size(); i++){
            int vecin = vecini[nod][i];
            if(!vizitat[vecin] && flux[nod][vecin] < capacitate[nod][vecin]){
                vizitat[vecin] = true;
                coada.push(vecin);
                tata[vecin] = nod;
            }
        }
    }
    return vizitat[destinatie];
}

int Graf :: fluxMaxim(const int sursa, const int destinatie) {
    vector< vector<int> > flux(n + 1), capacitate(n + 1);
    vector<int> tata;
    vector<bool> vizitat;
    int total = 0;
    for (int i = 1; i <= n; i++) {
        flux[i].resize(n + 1);
        capacitate[i].resize(n + 1);
    }
    for (int i = 0; i < muchiiCapacitate.size(); i++) {
        capacitate[ muchiiCapacitate[i].x ][ muchiiCapacitate[i].y ] = muchiiCapacitate[i].capacitate;
    }
    while(bfsFlux(sursa, destinatie, flux, capacitate, tata, vizitat)){
        for(int i = 0; i < vecini[destinatie].size(); i++){
            int vecin = vecini[destinatie][i];
            if(vizitat[vecin] && capacitate[vecin][n] > flux[vecin][n]){
                int minim = capacitate[ vecin ][destinatie] - flux[ vecin ][destinatie];
                int p = vecin;
                while(tata[p] > 0){
                    minim = min(minim, capacitate[ tata[p] ][ p ] - flux[ tata[p] ][ p ]);
                    p = tata[p];
                }
                total += minim;
                flux[vecin][destinatie] += minim;
                flux[destinatie][vecin] -= minim;
                p = vecin;
                while(tata[p] > 0){
                    flux[ tata[p] ][p] += minim;
                    flux[ p][ tata[p] ] -= minim;
                    p = tata[p];
                }
            }
        }
    }
    return total;
}

vector<int> Graf :: cicluEulerian() {
    vector< vector<pair<int, int>> > veciniMuchie(n + 1);
    vector<bool> muchieAdaugata(m + 1);
    vector<int> ciclu;
    stack<int> stiva;
    int indiceMuchie = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < vecini[i].size(); j++) {
            if (vecini[i][j] >= i) {
                indiceMuchie++;
                int vecin = vecini[i][j];
                veciniMuchie[i].push_back(make_pair(vecin, indiceMuchie));
                veciniMuchie[vecin].push_back(make_pair(i, indiceMuchie));
                if (vecini[i][j] == i) {
                    j++;
                }
            }
        }
    }
    int nod;
    for (int i = 1; i <= n; i++) {
        if (vecini[i].size() != 0) {
            nod = i;
            if (vecini[i].size() % 2 == 1) {
                ciclu.push_back(-1);
                return ciclu; // Nu se poate obtine ciclu eulerian, se va returna un vector cu un singur element -1
            }
        }
    }
    stiva.push(nod);
    while (!stiva.empty()) {
        nod = stiva.top();
        int i = veciniMuchie[nod].size() - 1;
        while (i >= 0 && muchieAdaugata[ veciniMuchie[nod][i].second ]) {
            veciniMuchie[nod].pop_back();
            i--;
        }
        if (veciniMuchie[nod].size() == 0) {
            ciclu.push_back(nod);
            stiva.pop();
        }
        else {
            muchieAdaugata[ veciniMuchie[nod][i].second ] = true;
            stiva.push(veciniMuchie[nod][i].first);
            veciniMuchie[nod].pop_back();
        }
    }
    ciclu.pop_back();
    if (ciclu.size() != m) {
        ciclu.clear();
        ciclu.push_back(-1);
    }
    return ciclu;
}

int Graf :: costCicluHamiltonian() {
    //vector< vector<int> > dp(1 << n);
    const int inf = 1000000000;
    int dp[100][100];
    for (int i = 0; i < (1 << n); i++) {
        //dp[i].resize(n);
        for (int j = 0; j < n; j++) {
            dp[i][j] = inf;
        }
    }
    dp[1][0] = 0;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ( ( (i >> j) & 1) == 1 ) {
                for (int k = 0; k < veciniCost[j + 1].size(); k++) {
                    int vecin = veciniCost[j + 1][k].first - 1;
                    if ( ( (i >> vecin) & 1) == 0) {
                        dp[i + (1 << vecin)][vecin] = min(dp[i + (1 << vecin)][vecin],
                                                      dp[i][j] + veciniCost[j + 1][k].second);
                    }
                }
            }
        }
    }
    int sol = inf;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < veciniCost[i].size(); j++) {
            if (veciniCost[i][j].first == 1) {
                sol = min(sol, dp[(1 << n) - 1][i - 1] + veciniCost[i][j].second);
            }
        }
    }
    return sol;
}

bool havelHakimi(int n, vector<int> g) {
    int i, ii, k;
    vector<int> fr, fr2;
    fr.resize(n);
    fr2.resize(n);
    for (i = 1; i <= n; i++) {
        if (g[i] < 0 || g[i] >= n) {
            return false;
        }
        fr[ g[i] ]++;
    }
    for (ii = 1; ii <= n; ii++) {
        for (i = n - 1; i >= 1; i--) {
            if (fr[i] > 0) {
                k = i;
                break;
            }
        }
        if (i == 0) {
            return true;
        }
        fr[k]--;
        for (; i >= 1; i--) {
            if (fr[i] < k) {
                k -= fr[i];
                fr2[i - 1] = fr[i];
            }
            else {
                fr2[i - 1] = k;
                fr2[i] += fr[i] - k;
                k = 0;
                break;
            }
        }
        for (i = i - 1; i >= 0; i--) {
            fr2[i] += fr[i];
        }
        if (k > 0) {
            return false;
        }
        for (i = 0; i < n; i++) {
            fr[i] = fr2[i];
            fr2[i] = 0;
        }
    }
}

int main() {
    int n, m;
    muchieCost muchii[400];
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>> n >> m;
    for (int i = 1; i <= m; i++) {
        fin>> muchii[i].x >> muchii[i].y >> muchii[i].cost;
        muchii[i].x++;
        muchii[i].y++;
    }
    Graf *graf = new Graf(n, m, muchii, true);
    fout<< graf->costCicluHamiltonian();
    return 0;
}