#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int t[200005],i,n,m,t1,t2,r,j,n1,n2,cost;
struct ceva
{
    int x,y,c;
}v[400005];
vector <int> vr;
ifstream in("apm.in");
ofstream out("apm.out");

bool comp(ceva i,ceva j)
{
    return (i.c<j.c);
}
int tata(int p)
{
    if (p==t[p]) return p;
    else tata(t[p]);
}
void reuniune()
{
    t[tata(t1)]=tata(t2);
}
int main()
{
    in>>n>>m;
    for (i=1;i<=m;i++)
    {
        in>>v[i].x>>v[i].y>>v[i].c;
    }
    for (i=1;i<=n;i++) t[i]=i;
    sort(v+1,v+m+1,comp);
    //for (i=1;i<=m;i++) cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].c<<endl;
    r=n-1;i=0;j=0;
    while (r)
    {
        i++;
        n1=v[i].x;
        n2=v[i].y;
        t1=tata(n1);
        t2=tata(n2);
        if (t1!=t2)
        {
            reuniune();
            cost+=v[i].c;
            r--;
            vr.push_back(i);
        }
    }
    out<<cost<<endl;
    out<<n-1<<endl;
    for (i=0;i<=n-2;i++) out<<v[vr[i]].x<<" "<<v[vr[i]].y<<endl;
}