#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 200005
#define MMAX 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y,c;
}v[MMAX];
int n,m,tata[NMAX],rang[NMAX];
bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}
int cauta(int nod)
{
    while(nod!=tata[nod])
        nod=tata[nod];
    return nod;
}
void unire(int x,int y)
{
    if(rang[x]>rang[y])
    {
        tata[y]=x;
        rang[y]=rang[x];
    }
    else if(rang[x]<rang[y])
    {
        tata[x]=y;
        rang[x]=rang[y];
    }
    else
    {
        tata[x]=y;
        rang[y]++;
    }
}
pair<int,int>sol[MMAX];
void kruskal()
{
    int s,k;
    s=k=0;
    for(int i=1;i<=m;i++)
    {
        int a=cauta(v[i].x),b=cauta(v[i].y);
        if(a!=b)
        {
            unire(a,b);
            s+=v[i].c;
            k++;
            sol[k].first=v[i].x;
            sol[k].second=v[i].y;
        }
    }
    fout<<s<<'\n';
    fout<<n-1<<'\n';
    for(int i=1;i<=k;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<'\n';
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++)
        {tata[i]=i;rang[i]=1;}
    kruskal();
    return 0;
}