#include <iostream>

using namespace std;
struct Nod{
    int ranq;
    Nod parent;
    };
Nod c[200005];
Nod makeset(int x){
Nod k;
k.parent=k;
k.ranq=0;
return k;
}
Nod findset(Nod x){
if (x.parent!=x) x.parent=findset(x.parent);
return x.parent;
}
void Union(Nod x, Nod y){
Nod xroot, yroot;
xroot=findset(x);
yroot=findset(y);
if (xroot==yroot) return;
if (xroot.ranq<yroot.ranq)
     xroot.parent=yroot;
else if (xroot.ranq>yroot.ranq)
    yroot.parent=xroot;
else {xroot.parent=yroot;
      yroot.ranq++;
}
}
int main()
{ ifstream fin("apm.in");
     ofstream fout("apm.out");

    int Nr;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>Muchii[i].e1>>Muchii[i].e2>>Muchii[i].cost;
    for(int i=1; i<=n; i++)
        c[i]=makeset(i);
    Sortare(1,m);
    Nr=0;
    for(int i=1; Nr<n-1; i++)
    if(c[Muchii[i].e1]!=c[Muchii[i].e2]){
    A[++Nr]=i;
    Union(c[Muchii[i].e1],c[Muchii[i].e2]);
        }
        int cost=0;
        for(int i=1; i<n; i++)
    cost+=Muchii[A[i]].cost;
        fout<<cost<<endl;
        fout<<Nr<<endl;

    for(int i=1; i<n; i++)
  fout<<Muchii[A[i]].e2<<" "<<Muchii[A[i]].e1<<endl;




    return 0;
}