#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];
vector <int> b;

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);

 for(int i=1;i<=m;++i)
   if(L[a[i].s]!=L[a[i].d])
   {
       b.push_back(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 j=1;j<=n;++j)
        if(L[j]==maxi)
         L[j]=mini;
   }

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





}