#include <fstream>
#include <algorithm>
using namespace std;
int t[100005],h[100005];
struct pct
{
    int x,y,c;
    bool viz;
};
pct v[200001];
bool comp(pct a,pct b)
{
    return a.c<b.c;
}
int findset(int x)
{
  while(t[x]!=x)
        x=t[x];
  return x;
}
void unionset(int x,int y)
{
    if(h[x]==h[y])
    {
     h[x]++;
     t[y]=x;
    }
    else
     if(h[x]<h[y])
         t[x]=y;
    else
        t[y]=x;

}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n,m,i,j,cost=0;
        in>>n>>m;
        for(i=1;i<=n;i++){
            t[i]=i;
        }
        for(i=1;i<=m;i++){
            in>>v[i].x>>v[i].y>>v[i].c;
        }
    sort(v+1,v+m+1,comp);
        for(i=1;i<=m;i++){
            if(findset(v[i].x)!=findset(v[i].y))
            {
                unionset(findset(v[i].x),findset(v[i].y));
                cost+=v[i].c;
                v[i].viz=1;
            }
        }
    out<<cost<<"\n"<<n-1<<"\n";
        for(i=1;i<=m;i++){
            if(v[i].viz) out<<v[i].y<<" "<<v[i].x<<"\n";
        }
    return 0;
}