#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,cost;
struct muchie{

  int cost,s,d;

} a[400010];
int L[200001],R[200001];
vector <int> b;

bool comp(muchie i, muchie j)
{
    return (i.cost<j.cost);
}

int rad(int fr){
    int x = fr;
    while(L[x]){
        x = L[x];
    }
    return x;
}

int main()
{
 f>>n>>m;

 for(int i=1;i<=n;++i)
    R[i]=i;

 for(int i=1;i<=m;++i)
    f>>a[i].s>>a[i].d>>a[i].cost;

 sort(a+1,a+1+m,comp);

 for(int i=1;i<=m;++i)
 {
     int Rx=rad(a[i].s);
     int Ry=rad(a[i].d);
   if(Ry!=Rx)
   {
       b.push_back(i);
       cost+=a[i].cost;

       if(R[Rx]>R[Ry])
       {
           R[Rx] += R[Ry];
                L[Ry] = Rx;
       }
       else
       {
           R[Rx] += R[Ry];
                L[Ry] = Rx;
       }
   }

 }
   g<<cost<<'\n'<<n-1<<'\n';
   for(int i=0;i<n-1;++i)
    g<<a[b[i]].d<<" "<<a[b[i]].s<<'\n';





}