#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct elem
{
    int inc;
    int sf;
    int price;
};
vector<elem>rez;
elem v[200005];
bool cmp(elem x,elem y)
{
    return x.price<y.price;
}
int tata[200005],rang[200005];
int find1(int x)
{
    int reprezentant=x;
    while(tata[reprezentant]!=reprezentant)
    {
        reprezentant=tata[reprezentant];
    }
    while(tata[x]!=x)
    {
        int copie=tata[x];
        tata[x]=reprezentant;
        x=copie;
    }
    return reprezentant;
}
void union1(int reprez1,int reprez2)
{
    if(rang[reprez1]==rang[reprez2])
    {
        tata[reprez1]=reprez2;
        rang[reprez2]++;
    }
    else if(rang[reprez1]<rang[reprez2])
    {
        tata[reprez1]=reprez2;
    }
    else if(rang[reprez1]>rang[reprez2])
    {
        tata[reprez2]=reprez1;
    }
}
int main()
{
    int n,m;
    in>>n>>m;
    for(int i=1;i<=n;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        in>>v[i].inc>>v[i].sf>>v[i].price;
    }
    sort(v+1,v+m+1,cmp);
    long long sumamuchii=0;
    for(int i=1;i<=m;i++)
    {
        if(find1(v[i].inc)!=find1(v[i].sf))
        {
            union1(find1(v[i].inc),find1(v[i].sf));
            elem newfound;
            newfound.inc=v[i].inc;
            newfound.sf=v[i].sf;
            newfound.price=v[i].price;
            rez.push_back(newfound);
            sumamuchii+=newfound.price;

        }
    }
    out<<sumamuchii<<'\n';
    out<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        out<<rez[i].inc<<' '<<rez[i].sf<<'\n';
    return 0;
}