#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct Nod{
    int n;
    int w;
};

struct Muchie{
    int x,y,w;


};
bool operator < (const Muchie n, const Muchie m){
        return (n.w>m.w);
}
vector<vector<Nod>> L;
vector<int> Noduri_comp;
vector<Muchie> L_muchii;



int uFind(int n, vector<int> &VTati){
    vector<int> noduri_parcurse;

    int temp  = n;
    while(temp!=VTati[temp]){
        noduri_parcurse.push_back(temp);
        temp=VTati[temp];
    }
    for(int e:noduri_parcurse){
        VTati[e] =  temp;
    }
    return temp;

}

void uUnion(int x, int y, vector<int> &VTati){
    int tataX = uFind(x,VTati);
    int tataY = uFind(y,VTati);
    VTati[tataX] = tataY;
}


void citire(){
    int n,m;
    in>>n>>m;

    L.resize(n+1);
    Noduri_comp.resize(n+1);
    for(int i=1;i<n+1;i++){
        Noduri_comp[i] = i;
    }
    for(int i=0;i<m;i++){
        int x,y,w;
        in>>x>>y>>w;
        Muchie m;
        m.x=x;
        m.y=y;
        m.w=w;
        L_muchii.push_back(m);
        Nod tmp;
        tmp.n = y;
        tmp.w = w;
        L[x].push_back(tmp);
        tmp.n = x;
        tmp.w = w;
        L[y].push_back(tmp);
    }
}
void prim(){
    int cost_total = 0;
    vector<Muchie> rez;
    priority_queue<Muchie> pq;
    queue<int> q;
    vector<int> viz;
    viz.resize(L.size());
    for(auto &e:viz ){e=0;}

    q.push(1);
    viz[1]=1;
    while(!q.empty()){
        int actual = q.front();
        q.pop();
        for(auto vecin : L[actual]){
            if(viz[vecin.n]==0){
                Muchie m;
                m.w=vecin.w;
                m.y=vecin.n;
                m.x=actual;
                pq.push(m);
            }
        }
        Muchie smallest;
        do{
            smallest=pq.top();
            pq.pop();
        }while(viz[smallest.y]!=0 && !pq.empty());
        if(viz[smallest.y]==0){
        rez.push_back(smallest);
        cost_total+=smallest.w;
        q.push(smallest.y);
        viz[smallest.y] = 1;
        }
    }
    out<<cost_total<<'\n';
    out<<rez.size()<<'\n';
    for(auto e:rez){
        out<<e.x<<' '<<e.y<<'\n';
    }

}





int main(){
    citire();
    prim();

}