#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],b[400010];

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

int main()
{
 f>>n>>m;
 for(int i=1;i<=n;++i)
    L[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);

 int nrelem=0;

 for(int i=1;nrelem<n-1;++i)
   if(L[a[i].s]!=L[a[i].d])
   {
       b[++nrelem]=i;
       cost+=a[i].cost;
       int mini=min(L[a[i].s],L[a[i].d]),maxi=max(L[a[i].s],L[a[i].d]);
       for(int i=1;i<=n;++i)
        if(L[i]==maxi)
        L[i]=mini;
   }

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





}