#include <bits/stdc++.h>

using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
#define MMAX 400005
pair<int,int>p[MMAX];
int n,m,k,total,t[MMAX],rg[MMAX];
struct muchie{
    int x,y,cost;
}v[MMAX];
bool compare(muchie a,muchie b)
     {
         return a.cost<b.cost;
     }
void read()
    {
        f>>n>>m;
        for(int i=1;i<=m;i++)
            f>>v[i].x>>v[i].y>>v[i].cost;
        sort(v+1,v+m+1,compare);
    }
int cauta(int nod)
    {
      while(t[nod]!=nod)
            nod=t[nod];
      return nod;
    }
void unite(int x,int y)
     {
         if(rg[x]<rg[y])
            t[x]=y;
         else
            if (rg[x]>rg[y])
                t[y]=x;
         else
            if (rg[x]==rg[y])
                {
                  t[x]=y;
                  rg[y]++;
                }
     }
void solve()
     {
         for (int i=1;i<=m;i++)
                {
                  if(cauta(v[i].x)!=cauta(v[i].y))
                  {
                      unite(cauta(v[i].x),cauta(v[i].y));
                      p[++k].first=v[i].x;
                      p[k].second=v[i].y;
                      total=total+v[i].cost;

                  }
                }
     }
int main()
{
    read();
    for (int i=1;i<=n;i++)
    {
        t[i]=i;
        rg[i]=1;
    }
    solve();
    g<<total<<'\n';
    g<<n-1<<'\n';
    for(int i=1;i<=k;i++)
         g<<p[i].first<<" "<<p[i].second<<'\n';
    return 0;
}