#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <int> afis1;
vector <int> afis2;
int k[200001],c[400001],t[200001],v1[400001],v2[400001],z[400001],n,m,a,b,t1,t2,cost;
int tata(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
bool cmp(int x,int y)
{
    return c[x]<c[y];
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
      f>>v1[i]>>v2[i]>>c[i];
    for(int i=1;i<=m;i++)
        z[i]=i;
    for(int i=1;i<=n;i++)
        k[i]=1,t[i]=i;
    sort(z+1,z+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
    t1=tata(v1[z[i]]);t2=tata(v2[z[i]]);
     if(t1!=t2)
     {
        cost=cost+c[z[i]];
         if(k[t1]>=k[t2])
      {
          k[t1]=k[t1]+k[t2];
          t[t2]=t1;
      }
      else
      {
          k[t2]=k[t1]+k[t2];
          t[t1]=t2;
      }
      afis1.push_back(v1[z[i]]);
      afis2.push_back(v2[z[i]]);
     }
    }
    g<<cost<<'\n';
    g<<afis1.size()<<'\n';
    for(int i=0;i<afis1.size();i++)
        g<<afis1[i]<<" "<<afis2[i]<<'\n';
    return 0;
}