#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
#define MMax 400000
using namespace std;
struct muchie{
    int x, y, c;
    bool viz=false;
    muchie(){};
    muchie(int _x, int _y, int _c){x=_x; y=_y; c=_c;};
};
int n, m;
vector<muchie> G;
vector<int> c;
vector<int> A;
bool cmpM(muchie m1, muchie m2){
    return m1.c<m2.c;
}
void citire(){
    ifstream f("apm.in");
    int x,y,cost;
    f>>n>>m;
    c=vector<int>(n+1);
    A=vector<int>(n+1, 0);
    while(f>>x>>y>>cost)
        G.push_back(muchie(x,y,cost));
    for(int i=1;i<=n;i++)
        c[i]=i;
}
void afisare(){

}
int main(){
    citire();
    sort(G.begin(), G.end(), cmpM);
    int nrMSel=0, m1, m2, cost=0;
    int i=0;

    /*cout<<"Muchii sortate:\n";
    for(int i=0;i<m;i++)
        cout<<G[i].x<<" "<<G[i].y<<" "<<G[i].c<<"\n";
    cout<<"\n";
*/

    while(nrMSel<n-1 && i<m){
        if(c[G[i].x]!=c[G[i].y]){
            A[nrMSel++]=i;
            cost+=G[i].c;
            m1=min(c[G[i].x], c[G[i].y]);
            m2=max(c[G[i].x], c[G[i].y]);
            for(int j=1;j<=n;j++)
                if(c[j]==m2)
                    c[j]=m1;
            /*cout<<"added "<<G[i].x<<"-"<<G[i].y<<" "<<G[i].c<<"\n";
            cout<<"m1="<<m1<<" m2="<<m2<<"\n";
            cout<<"c=[";
            for(int i=1;i<=n;i++)
                cout<<c[i]<<" ";
            cout<<"]\n";
            cout<<"----\n";*/
        }
        i++;
    }
    ofstream g("apm.out");
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
        g<<G[A[i]].y<<" "<<G[A[i]].x<<"\n";
    afisare();




    return 0;
    for(int i=0;i<=m;i++)
        cout<<G[i].x<<" "<<G[i].y<<" "<<G[i].c<<"\n";

    return 0;
}