#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. Acest criteriu sorteaza muchiile dupa cost
    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 ce suporta operatii de Union si GetRoot
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, care vor fi retinute doar la nevoie pentru a nu incarca memoria

    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

    int getPath(vector<int> &l, vector<int> &r, vector<bool> &seen, int node); //Functie de gasire a lanturilor alternante pentru cuplajul maxim in Graf Bipartit


public:

    Graph(int nodes, bool areLabeled, bool isDirected = false, bool needFlow = false);
    /**
     * constructor ce primeste parametrii:
        Nr de noduri
        Graful e sau nu etichetat
        Graful e sau nu orientat
        Avem nevoie sa retinem capaciatile si fluxurile de pe muchii
     **/

    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 de forma (nod1,nod2,cost), unde costul poate lipsi si este implicit 0


    vector<long long> dijkstra(int source); //Functie pentru algoritmul lui Dijkstra. Returneaza distantele de la un nod primit ca parametru la toate celelalte

    vector<int> bfs(int source); //BFS, returneaza distante (ca numar de muchii) de la un nod primit ca parametru la toate celelalte

    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(); //Returneaza componentele tare conexe


    vector<vector<int>> getBiconected(); //Returneaza Componentele Biconexe

    vector<pair<int, int>> getCriticalEdges(); //Returneaza un vector de Muchii Critice

    vector<int> getTopSort(); //Returneaza un vector ce reprezinta o Sortare Topologica valida

    static bool HavelHakimi(vector<int> degSequence); //Havel Hakimi, intoarce True/False daca o lista de grade primita ca input poate forma, sau nu, un graf


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

    getMST(); //APM cu Kruskal. Intoarce un pair {cost,muchii}, unde cost este costul APM-ului iar muchii este un vector de contine muchiile APM-ului

    pair<int, vector<long long> > bellmanFord(int source); //Bellmanford, intoarce un errorcode ce semnifica daca algoritmul s-a putut efectua
                                                            // sau nu si in caz afirmativ vectorul de distante de la un nod primit ca input la toate celelalte

    vector<vector<int>> royFloyd(); //RoyFloyd. Intoarce matricea de distante intre oricare 2 noduri din graf

    vector<int> getDepths(int root); //getDepths. Intoarce un vector cu adancimea fiecarui nod daca inradacinam arborele intr-un nod dat ca input

    int getTreeDiam(); //Intoarce un numar intreg ce reprezinta diametrul unui arbore


    int getMaxFlow(int source, int destination); //Intoarce un numar intreg ce reprezinta Fluxul Maxim / Taietura Minima

    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
    //Pentru ca algoritmul sa aiba randament mai bun, folositi indicii muchiilor drept costuri (memorie + timp)

    pair<int, vector<pair<int, int> > > getBipartiteMatching(int n, int m);
    //Se primesc lungimile celor 2 partitii ale unui graf bipartit si se returneaza cardinalul cuplajului maximal si muchiile acestuia

    int getHamiltonCycleCost();
    //Returneaza costul ciclului hamiltonian minim din graful apelant


};

int Graph::getHamiltonCycleCost() {


    /**
     * Se foloseste o dinamica pe stari exponentiale dp[mask][last_node], unde mask codeaza nodurile vizitate, iar last_node ultimul nod vizitat
     * Complexitate O(2^n*n^2)
     */
    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 = 2; 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;

}

int Graph::getPath(vector<int> &l, vector<int> &r, vector<bool> &seen, int node) {

    /*
     * Functie auxiliara pentru cuplaj. Incearca gasirea unui nou lant alternant sau extinderea unuia existent
     */
    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;

}

pair<int, vector<pair<int, int> > > Graph::getBipartiteMatching(int n, int m) {
    /**
     * Foloseste Algoritmul Hopcroft Karp bazat pe gasirea lanturilor de augmentare.
     * COmplexitate O(E sqrt(V))
     */
    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) {

    /**
     * DFS tipic de sortare topologica
     * Complexitate: O(n+m)
     */
    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) {

    /**
     * Algoritmul Tarjan pentru detectarea componentelor tare conexe, bazat pe nodul minim in care se poate intoarce orice nod.
     * Pentru acesta se utilizeaza stiva si nu se utilizeza graful transpus
     * Complexitate: O(n+m)
     */
    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) {

    /**
     * Algoritmul de determinare a componentelor biconexe
     * Acesta utilizeaza o logica asemanatoare cu algoritmul pentru componente tare conexe, bazat pe nodul de adancime minima la care se intoarce orice nod
     * Complexitate: O(n+m)
     */
    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) {
    /**
     * DFS.
     * Complexitate: O(n+m)
     */
    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) {

    /**
     * BFS folosit la algoritmul de flux.
     * Intoarce prin referinta un vector de tati aferent parcurgerii
     * Complexitate: O(n+m)
     */
    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) { //constructor
    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) {

    /**
     * Algoritmul lui Dijkstra folosindu-se heapuri binare
     * Complexitate: O((n+m)*log n)
     * Optimizabil la: O(m + nlog n) folosind heapuri fibonacci
     */

    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) {
    /**
     * BFS.
     * Complexitate: O(n+m)
     */
    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) {
    /**
     * Havel Hakimi. Bazat pe un algoritm de tip greedy de matching a nodurilor
     * Complexitate: O(n^2) cu interclasare in loc de sortari ulterioare
     */
    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;
}

/**
 * Functii ce returneaza rezultatele fiecarui algoritm
 *
 */
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() {
    /**
     * Muchiile critice sunt cele intre punctele de articulatie si fii sai care nu fac parte din aceeasi componenta biconexa
     */
    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]) swap(x,y);

        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() {
    /**
     * Folosim Algoritmul Kruskal pentru determinarea APM-ului
     * O(m log m + m log* n) folosind DSU cu euristicile de Road Compression si Rank Union, log* = inversul functiei Ackermann, aproximabil la O(1)
     */
    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) {
    /**
     * Algoritmul BellmanFord are o utilitate similara cu Dijkstra
     * Pentru el utilizam o coada in care retinem nodurile ce pot actualiza solutia
     * Acesta poate fi utilizat si pentru detectia ciclurilor negative
     * Complexitatea teoretica este de O(n*m), insa se comporta bine in practica
     */
    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() {
    /**
     * Algoritmul Roy Floyd calculeaza distantele intre oricare 2 noduri din graf
     * Complexitate: O(n^3)
     */
    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() {
    /**
     * Diametrul unui arbore afla folosind 2 parcurgeri DFS din 2 noduri distincte
     * Complexitate O(n+m)
     */
    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) {
    /**
     * Am utilizat algoritmul Edmonds Karp pentru aflarea fluxului maxim
     * Acesta gaseste drumuri de crestere pe care le satureaza
     * Complexitatea teoretica este de O(n*m^2), insa se comporta mai bine in practica
     *
     */

    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() {
    /**
     * Conditia necesara si suficienta pentru existenta unui ciclu eulerian intr-un graf este ca toate nodurile sa aiba grad par
     * Daca graful nostru indeplineste aceasta conditie, ciclul efectiv poate fi aflat folosind o parcugere DFS
     * COmplexitate: O(n+m), in cazul in care pentru fiecare muchie retinem indicele sau pentru a marca faptul ca a fost vizitata (eu am retinut acest lucru in campul cost)
     * Complexitate mai mare cu un factor de log n pentru rezolvarile cu set-uri/ map-uri
     */
    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();

    if (sol != (1e9))
        printf("%d\n", sol);
    else
        printf("Nu exista solutie\n");

    return 0;


}