#include <fstream>
#include <queue>
#define NMAX 400004

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{

    int x,y,c;
    friend bool operator >(const muchie &a, const muchie &b);
};

bool operator >(const muchie &a, const muchie &b){
    return a.c>b.c;
}

int tata[NMAX],h[NMAX];
int n,m;
priority_queue< muchie, vector<muchie>, greater<muchie> >H;
vector<muchie> v;

int Find(int x){
int rx=x,y;
while(tata[rx]) rx=tata[rx];
while(x!=rx){
    y=tata[x];
    tata[x]=rx;
    x=y;
}
    return rx;
}

void Union(int x, int y){
if(h[x]>h[y])
    tata[y]=x;
else
    if(h[x]<h[y])
        tata[x]=y;
    else{
        tata[y]=x;
        h[x]++;
    }
}
void kruskal(){
int nrsel=0,s=0,rx,ry;
muchie srt;
while(nrsel<n-1){
    srt=H.top(); H.pop();
    rx=Find(srt.x);
    ry=Find(srt.y);
    if(rx!=ry){
        Union(rx,ry);
        v.push_back(srt);
        nrsel++;
        s+=srt.c;
    }
}
 fout<<s<<'\n'<<nrsel<<'\n';
 for(int i=0;i<nrsel;i++)
    fout<<v[i].y<<' '<<v[i].x<<'\n';
}
int main()
{
    fin>>n>>m;
    muchie srt;
    for(int i=1;i<=m;i++){
        fin>>srt.x>>srt.y>>srt.c;
        H.push(srt);
    }
    kruskal();
    return 0;
}