#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int tata[200001],x,y,nod1,nod2,n,m,i,s,viz[400001],nr;
struct du{
    int x,y,cost;}muchii[400001];
int root(int x){
    while(tata[x]>0)
        x=tata[x];
    return x;
    }
int cmp(du u,du v){
    return u.cost<v.cost;}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
for(i=1;i<=n;i++)
    tata[i]=-1;
sort(muchii+1,muchii+m+1,cmp);
    for(i=1;i<=m&&(nr!=n-1);i++){
        nod1=muchii[i].x;
        nod2=muchii[i].y;
        nod1=root(nod1);
        nod2=root(nod2);
        if(nod1!=nod2){
                viz[i]=1;
                nr++;
        if(tata[nod2]<tata[nod1]){
            tata[nod2]+=tata[nod1];
            tata[nod1]=nod2;
    }
        else{
            tata[nod1]+=tata[nod2];
            tata[nod2]=nod1;
        }
        s+=muchii[i].cost;
        }
    }
    g<<s<<'\n';
    g<<nr<<'\n';
    for(i=1;i<=m;i++)
        if(viz[i]==1)
        g<<muchii[i].x<<" "<<muchii[i].y<<'\n';
    return 0;
}