#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
class muchie{
public:
    int cost;
    int x;
    int y;

    bool operator < (const muchie& m1) const
    {
        return (cost < m1.cost);
    }
};
muchie M [400001], A[200001];
unsigned int n, m;
int c, st=1, ucomp, vcomp, st2=1, sum;
unsigned int s[200001], h[200001];
int find3(int x)
{
    int r=x, j;
    while (s[r]!=r)
        r=s[r];
    int i = x;
    while (i!=r)
    {
        j=s[i];
        s[i]=r;
        i=j;
    }
    return i;
}
void reuniune3(int a, int b)
{
    if(h[a]==h[b])
    {
        ++h[a];
        s[b]=a;
    }
    else if (h[a]>h[b])
            s[b]=a;
        else
            s[a]=b;
}
int main ()
{
    ifstream in ("apm.in");
    ofstream out ("apm.out");
    in>>n>>m;
    for (int i=1;i<=m;++i)
        in>>M[i].x>>M[i].y>>M[i].cost;
    for(int i=1;i<=n;++i)
        s[i]=i;
    sort (M+1, M+m+1);
    while(c!=n-1)
    {
        ucomp=find3(M[st].x);
        vcomp=find3(M[st].y);
        if(ucomp!=vcomp)
        {
            reuniune3(ucomp, vcomp);
            A[st2]=M[st];
            sum+=M[st].cost;
            ++st2;
            ++c;
        }
        ++st;
    }
    out<<sum<<"\n";
    out<<c<<"\n";
    for(int i=1;i<=c;++i)
        out<<A[i].x<<" "<<A[i].y<<"\n";
    in.close();
    out.close();
    return 0;
}