//
//  main.cpp
//  APM
//
//  Created by Mara Dascalu on 01/11/2021.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bits/stdc++.h>
#include <map>
#include <list>
#include <set>
#include <tuple>

using namespace std;

ifstream input("apm.in");
ofstream output("apm.out");

class DisjointSets
{
    int no_nodes;
    vector<int> reprez;     //vectorul care retine reprezentantul fiecarui nod
    
public:
    
    void set_no_nodes(int nr) { no_nodes = nr;}
    int get_no_nodes() { return no_nodes;}
    
    void initialization(int no_node);      //creeaza o componenta cu un singur varf
    int reprezentative(int node);       //returneaza reprezentantul componentei care il contine pe node
    void reunite(int node1, int node2); //uneste componenta care contine node1 cu cea care contine node2
};

void DisjointSets::initialization(int no_node)
{
    set_no_nodes(no_nodes);
    
    reprez.push_back(0);
    for (int i = 1; i <= no_node; i++)
        reprez.push_back(i);
}

int DisjointSets::reprezentative(int node)
{
    return reprez[node];
}

void DisjointSets::reunite(int node1, int node2)
{
    int r1, r2;
    
    r1 = reprezentative(node1);
    r2 = reprezentative(node2);
    for (int i = 1; i <= get_no_nodes(); i++)
        if (reprez[i] == r2)
            reprez[i] = r1;
}

class Graph
{
    int nodes, edges;
    vector<int> adj[100010] ;
    bool visited[100010] = {0};
    
//    void sccUtil (int node, int disc[], int low[], stack<int> *st, bool stackMember[]);       //functia auxiliara pentru determinarea componentelor tare conexe
    void DFS(int node);     //parcurgerea DFS a grafului
    void afis_adj(int node);       //afisarea vectorului de vectori de adiacenta a nodurilor
    static bool sortByTh (const tuple<int,int,int> &a, const tuple<int,int,int>&b);    //sorteaza vectorul de tupluri coare contine si costul muchiilor dupa al treilea parametru (cost)

public:
    
    void set_no_nodes(int n) {nodes = n;}
    int get_no_nodes() {return nodes;}
    void set_no_edges(int n) {edges = n;}
    int get_no_edges() {return edges;}

    void addEdge_dg (int no_nodes, int no_edges);
    void addEdge_ug ();
    
    //PROBLEMA DFS INFOARENA: https://infoarena.ro/problema/dfs
    int connectedComponents ();     //determinarea numarului de componente conexe ale grafului

    //PROBLEMA BFS INFORARENA: https://infoarena.ro/problema/bfs
    void BFS (int node);    //BFS adaptat pentru a calcula costul de parcurgere al fiecarui nod, plecand dintr-un nod de start

    //PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
    void DFS(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current);     // DFS auxiliar pentru determinarea componentelor biconexe
    void biconnectedComponents();     //determina componentele biconexe ale unui graf

    //PROBLEMA COMPONENTE TARE CONEXE INFOARENA: https://infoarena.ro/problema/ctc
//    void scc();      //determinarea componentelor tare conexe ale unui graf
    
    //PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
    void calculateIndegree (int indegree[]);       //functie auxiliara sortarii topologice pentru calcularea gradului interior al fiecarui nod
    void topSort(int indegree[], queue<int> queue_ts);      //functia de sortare topologica
    void topologicalSort();
    
    //PROBLEMA HAVEL-HAKIMI
    bool graphExists (vector<int> degree_seq);      //functia care decide daca daca o secventa de numere poate sau nu poate reprezenta o secventa de noduri ale unui graf
    void inputArray (vector<int> &degree_seq);
    void Havel_Hakimi();
    
    //PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
    void inputAPM(vector<tuple<int,int,int>> &weight_edges);
    void APMUtil(vector<tuple<int,int,int>> &weight_edges);
    void APM();
    
}g;

//void Graph::sccUtil (int node, int disc[], int low[], stack<int> *st, bool stackMember[])
//    {
//        static int time = 0;
//        int current =0;
//
//        //initializare disc si low pentru nodul curent
//        disc[node] = low[node] = time++;
//        st->push(node);
//        stackMember[node] = true;
//
//        //parcurgem toti vecinii lui node
//        for (int i = 0; i < adj[node].size(); i++)
//        {
//            int adj_node = adj[node][i];
//
//            if (!disc[adj_node])  //daca vecinul nu a fost vizitat inca
//            {
//                sccUtil(adj_node, disc, low, st, stackMember);
//
//                low[node] = min(low[node], low[adj_node]); //verificam daca subarborele care are drep radacina adj_node are un drum catre un stramos al lui node
//            }
//            else if (stackMember)
//            {
//                low[node] = min(low[node], disc[adj_node]);  //facem update daca avem muchie de intoarcere
//            }
//        }

void Graph::DFS(int node)
{
    visited[node] = 1;
    output<<node<<" ";

    for (int i = 0; i < adj[node].size(); i++)
        if( !visited[adj[node][i]])
            DFS(adj[node][i]);
}

void Graph::afis_adj(int node){
    for (int i = 0; i < adj[node].size(); i++)
         cout<<adj[node][i]<<" ";
}

void Graph::addEdge_dg (int no_nodes, int no_edges)
{
//       int no_nodes, no_edges;
//       input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2;

    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2;
        adj[node1].push_back(node2);
    }
}

void Graph::addEdge_ug ()
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2;

    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2;
        adj[node1].push_back(node2);
        adj[node2].push_back(node1);
    }
}

int Graph::connectedComponents ()
{
    int cc = 0;
    for (int i = 1; i <= get_no_nodes(); i++)
        if (!visited[i])
        {
            cc++;
            DFS(i);
        }
    return cc;
}

void Graph::BFS (int node)
{
    int cost[100010];
    queue<int> queue_bfs;
   
    memset(cost,  -1, sizeof(cost));
    
    visited[node] = 1; //marchez nodul curent ca vizitat
    queue_bfs.push(node);
    cost[node] = 0;

    while (!queue_bfs.empty()) {
        node = queue_bfs.front(); //iau nodul din varful cozii
        queue_bfs.pop();

        for (int i = 0; i < adj[node].size(); i++) //parcurg toti vecinii sai
            if ( !visited[adj[node][i]]) //daca sunt nevizitati
            {
                visited[adj[node][i]] = 1;  //ii marchez ca vizitati
                queue_bfs.push(adj[node][i]);   //ii adaug in coada
                cost[adj[node][i]] = cost[node] + 1;   //calculez costul raportat la "parintele" sau
            }
    }
   
    for (int i = 1; i <= get_no_nodes(); i++)
        output<<cost[i]<<" ";
}

void Graph::DFS(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current)
{
    visited[node] = 1;
    
    level[node] = level[parent] + 1;
    low_level[node] = level[node];
    int child;

    int dim = adj[node].size();
    for ( int i = 0; i< dim ; i++)
    {
        child = adj[node][i];
        if (child != parent)
        {
            if (visited[child] == true)  //daca fiul sau a fost deja parcurs si nu este tatal nodului curent, muchia (fiu,nod) este muchie de intoarcere
            {
                //cout<<"true "<<node<<" "<<*iter<<" "<<level[*iter]<<"\n";
                if(level[child] < low_level[node])low_level[node] = level[child];  //actualizam valoarea low_level[nod] daca fiul sau se afla mai sus decat el (p[t ca avem muchie de intoarcere
            }
            else //daca fiul sau nu a fost inca parcurs, continuam DFS din fiu
            {
                component_node.push({node, child});
                //cout<<"inainte de dfs"<<node<<" "<<*iter<<" "<<level[*iter]<<"\n";
                DFS(child, node, level, low_level, bcc, component_node, current);

                //cout<<"dupa dfs"<<*iter<<" "<<level[*iter]<<"\n";
                if (low_level[child] < low_level[node])
                    low_level[node] = low_level[child]; //daca la intoarcerea din apel fiul are un nivel de intoarcere mai mic decat al nodului, actualizam low_level[node]

                if (low_level[child] >= level[node])
                {
                    bcc.push_back({});
                    while( component_node.top().first != node)
                    {
                        bcc.back().push_back(component_node.top().second);
                        component_node.pop();
                    }
                    bcc.back().push_back(component_node.top().second);
                    bcc.back().push_back(component_node.top().first);
                    component_node.pop();
                    current++;
               }
            }
        }
    }
}

void Graph::biconnectedComponents()
{
    int level[100010] = {0};    //nivelul la care se afla un nod
    int low_level[100010] = {0};    //nivelul minim de intoarcere a unui nod
    stack<pair<int, int>> component_node;
    vector<vector<int>> bcc; //vectorul care stocheaza componentele biconexe
    int current = 0;
    
    DFS(1,0, level, low_level, bcc, component_node, current);
    
    output<<current << "\n";
    for (int i =0 ; i <= current; i++)
        {
            for (int j = bcc[i].size() - 1; j >= 0; j--)
                if(bcc[i][j])
                    output<<bcc[i][j]<<" ";
            output<<"\n";
        }
}

//void Graph::scc()
//    {
//        int dim = get_no_nodes();
//        int *disc = new int[dim]; //memoreaza timpul de descoperire al fiecarui nod
//        int *low = new int[dim]; //memoreaza timpul de descoperire minim care poate fi accesat din subarborele care are radacina in fiecare nod
//        bool *stackMember = new bool[dim]; //pentru verificarea mai rapida daca un nod este sau nu in stiva
//        stack<int> *st = new stack<int>();  //pentru stocarea compo\ conexe
//
//        for (int i = 0; i < dim ; i++)
//        {
//            disc[i] = low[i] = 0;
//            stackMember[i] = false;
//        }
//
//        //apelam recursiv sccUtil pentru gasirea comp tare conexe
//        for (int i = 1; i <= dim; i++)
//            if(!disc[i])
//                sccUtil(i, disc, low, st, stackMember);
//    }

//    void output_scc ()
//    {
//        output<<current<<"\n";
//        for (int i = current - 1; i >= 0 ; i--)
//        {
//            for (int j = 0; j < vec_scc[i].size(); j++)
//                output<<vec_scc[i][j]<<" ";
//            output<<"\n";
//        }
//    }

void Graph::calculateIndegree (int indegree[])
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);

    int node1, node2;
    memset(indegree, 0, no_nodes);
    
    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2;
        adj[node1].push_back(node2);
        indegree[node2]++;
    }
}

void Graph::topSort(int indegree[], queue<int> queue_ts)
{
    int dim = get_no_nodes();
    for (int i = 1; i <= dim ; i++)  //adaugam in coada doar nodurile care au gradul 0
    {
        if (indegree[i] == 0)
            queue_ts.push(i);
    }

    while (!queue_ts.empty()) //cat timp coada nu este goala, extragem varful, scadem gradele nodurilor adiacente cu varful si adaugam in coada acele noduri care au gradul interior 0
    {
        int node = queue_ts.front();
        queue_ts.pop();

        for (int i = 0; i < adj[node].size(); i++)
        {
            int adj_node = adj[node][i];
            indegree[adj_node]--;
            if (!indegree[adj_node])
                queue_ts.push(adj_node);
        }
        cout<<node<<" ";
    }
}

void Graph::topologicalSort()
{
    queue<int> queue_ts; //coada in care vom adauga doar nodurile care au gradul interior 0
    int indegree[100010] ; //vectorul care retine gradul interior al fiecarui nod
    
    calculateIndegree(indegree);
    topSort(indegree, queue_ts);
}

bool Graph::graphExists (vector<int> degree_seq)
{
    while (1) {
        sort(degree_seq.begin(), degree_seq.end(), greater<>());
        cout<<degree_seq[0]<<" ";
        if (degree_seq[0] == 0)  //daca toate elementele ramase sunt 0, atunci se poate construi un graf
            return true;
        
        int top = degree_seq[0];
        degree_seq.erase(degree_seq.begin());
        
        if (top > degree_seq.size()) // daca valoarea primului element este mare decat numarul de elemente ramase, nu putem construi un astfel de graf
            return false;
        
        for (int i = 0 ; i < degree_seq.size(); i++) //dupa eliminarea primului element, scadem gradul "nodurilor" ramase
        {
            degree_seq[i]--;
            if(degree_seq[i] < 0)  //daca apar numere negative, nu putem sa construim un graf
                return false;
        }
    }
}

void Graph::inputArray (vector<int> &degree_seq)
{
    int n;
    input>>n;
    
    for (int i = 0; i < n; i++)
    {
        int val;
        input>>val;
        degree_seq.push_back(val);
    }
}

void Graph::Havel_Hakimi()
{
    vector<int> degree_seq; //vectorul care contine gradele unui posibil graf
    
    inputArray(degree_seq);
    output<<graphExists(degree_seq);
}

bool Graph::sortByTh (const tuple<int,int,int> &a, const tuple<int,int,int>&b)
{
    return (get<2>(a) < get<2>(b));
}

void Graph::inputAPM(vector<tuple<int,int,int>> &weight_edges)
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);
    
    for (int i = 0 ; i < no_edges; i++)
    {
        int n1, n2, weight;
        input>>n1>>n2>>weight;
        weight_edges.push_back(make_tuple(n1,n2,weight));
    }
}

void Graph::APMUtil(vector<tuple<int,int,int>> &weight_edges)
{
    sort(weight_edges.begin(), weight_edges.end(), sortByTh);
    
    DisjointSets djs;
    djs.initialization(get_no_nodes());
    
    int weight = 0;     //costul arborelui
    int ctr = 0;        //numarul de muchii ale APM intr-un anumit moment
    vector<tuple<int,int>> apm;
    for (int i = 0; i < get_no_edges(); i++)
    {
        int n1 = get<0>(weight_edges[i]);
        int n2 = get<1>(weight_edges[i]);
        
        int r1 = djs.reprezentative(n1);
        int r2 = djs.reprezentative(n2);
        
        if (r1 != r2)
        {
            apm.push_back(make_tuple(n1, n2));
            ctr++;
            weight += get<2>(weight_edges[i]);
            djs.reunite(n1, n2);
            
            if  (ctr == get_no_nodes() - 1)      //un arbore poate avea maximum n-1 muchii intre noduri; astfel, daca am gasit n-1 muchii putem opri cautarea
                break;
        }
    }
    
    output<<weight<<"\n";
    output<<get_no_nodes() - 1<<"\n";
    for (int i = 0; i < apm.size(); i++)
        output<<get<0>(apm[i])<<" "<<get<1>(apm[i])<<"\n";
}

void Graph::APM()
{
    vector<tuple<int,int,int>> weight_edges;
    
    inputAPM(weight_edges);
    APMUtil(weight_edges);
    
}

int main(int argc, const char * argv[]) {
    g.APM();
}