#include <bits/stdc++.h>
  
using namespace std;
  
  
  
struct nod{
    int sur,dest,len;
  
};
nod a[400100],rs[400100];
int p[400100],n,m,sum;
  
int find1(int nod){
    if (p[nod]==nod) return nod;
    else{
        int x=find1(p[nod]);
        p[nod]=x;
        return x;
    }
  
}
  
void unite(int a,int b){
    a=find1(a);
    b=find1(b);
    p[a]=b;
}
  
bool comp(nod a, nod b){
    return a.len<b.len;
}
int N,M;
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >>N>>M;
    for(int i=1;i<=M;i++){ fin >>a[i].sur>>a[i].dest>>a[i].len;
  //  fout <<a[i].sur<<" "<<a[i].dest<<" "<<a[i].len<<endl;
}
  
    sort(a+1,a+M+1,comp);
    int sum=0;
    for(int i=1;i<=M;i++) p[i]=i;
    for(int i=1;i<=M;i++){
        if (find1(a[i].sur)!=find1(a[i].dest)&&find1(a[i].dest)!=find1(a[i].sur)) {
            rs[++n]=a[i];
            sum+=a[i].len;
            //fout <<a[i].sur<<" "<<a[i].dest<<endl;
            unite(a[i].sur,a[i].dest);
  
        }
  
    }
    //cout <<sum;
    fout <<sum<<endl<<n<<endl;
    for(int i=1;i<=n;i++) fout<<rs[i].sur<<" "<<rs[i].dest<<'\n';
    return 0;
}