#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
int tt[400005],rg[400005],n,m,i,cost;
vector<int> v1,v2;
struct muchie
{
    int a,b,c;
}v[400005];
bool comp(muchie x,muchie y)
{
    return x.c<y.c;
}
int cauta(int x)
{
    int y=x,aux;
    while(tt[x]!=x)
        x=tt[x];
    while(tt[y]!=x)
    {
        aux=tt[y];
        tt[y]=x;
        y=aux;
    }
    return x;
}
void uneste(int a,int b)
{
    if(rg[a]>rg[b]) {tt[b]=a;}
    else tt[a]=b;
    if(rg[a]==rg[b]) rg[b]++;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].c;


    }
    for(i=1;i<=n;i++) tt[i]=i;
    sort(v+1,v+m+1,comp);
    for(i=1;i<=m;i++)
    {
        if(cauta(v[i].a)!=cauta(v[i].b))
        {
         uneste(cauta(v[i].a),cauta(v[i].b));
         cost+=v[i].c;
         v1.push_back(v[i].a);
         v2.push_back(v[i].b);
        }
    }
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(i=0;i<n-1;i++)
    {
        g<<v1[i]<<' '<<v2[i]<<'\n';
    }
    return 0;
}