#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int nr,pad[400001],suma;
struct tt{
    int x,y,c;
    bool viz;
}a[200001];
bool criteriu(tt n1,tt n2){
    return n1.c<n2.c;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].x>>a[i].y>>a[i].c;
    }
    for(int i=1;i<=n;i++)
        pad[i]=-1;
    sort(a+1,a+m+1,criteriu);
  int  i=1;
    while(nr<n-1){
        int x1=a[i].x,y1=a[i].y;
        int xx=x1,yy=y1;
        while(pad[xx]>0)
            xx=pad[xx];
        while(pad[yy]>0)
            yy=pad[yy];
        if(xx!=yy){
            suma+=a[i].c;
             a[i].viz=1;
               nr++;
            if(pad[xx]<pad[yy]){
                pad[xx]+=pad[yy];
                pad[yy]=xx;
            }
            else{
                pad[yy]+=pad[xx];
                pad[xx]=yy;
            }
        }
      i++;
    }
    cout<<suma<<"\n"<<n-1<<"\n";
    for(int i=1;i<=m;i++)
        if(a[i].viz==1)
            cout<<a[i].x<<" "<<a[i].y<<"\n";
}