#include <fstream>
#include <algorithm>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
struct krusk{
int x; int y; int c;} a[400001];
int n, m, i,j,t[200001], sol1[200001], sol2[200001],s, u, d, e, aux;
bool ok;
bool cmpk(krusk h, krusk p)
{
    if(h.c>p.c) return false;
    return true;
}
int tata (int p)
{
    if(t[p]==p)
        return p;
    else return tata(t[p]);
}
int main()
{
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+m+1,cmpk);
    j=1;
    for(i=1;i<=n;i++)
    {
       t[i]=i;
    }
    for(i=1;i<n;i++)
    {
        ok=false;
        while(ok==false&&j<=m)
        {
            d=tata(a[j].x);
            e=tata(a[j].y);
            u=a[j].x;
            while (u!=d)
            {
                aux=t[u]; t[u]=d; u=t[u];
            }
            u=a[j].y;
            while (u!=e)
            {
                aux=t[u]; t[u]=e; u=t[u];
            }

            if(d!=e) ok=true;
            j++;
        }
        t[d]=e;
        s=s+a[j-1].c;
        sol1[i]=a[j-1].x;
        sol2[i]=a[j-1].y;
    }
    out<<s<<"\n";
    out<<n-1<<"\n";
    for(i=1;i<n;i++)
      out<<sol1[i]<<" "<<sol2[i]<<"\n";
    return 0;
}