#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct muchie
{
    int x,y,c;
}v[400001];
struct{
    int x,y;
}muchii[100001];
int tati[100001],rang[100001];
int cost,k;
int n,m;
bool comp(muchie a,muchie b)
{
    return a.c<b.c;
}
int Find(int nod)
{
    while(tati[nod]!=nod)
        nod=tati[nod];
    return nod;
}
void Unire(int x,int y)
{
    if(rang[x]<rang[y])
        tati[x]=y;
    else if(rang[x]>rang[y])
        tati[y]=x;
    else
    {
        tati[x]=y;
        rang[y]++;
    }
}
void rez()
{
    for(int i=1;i<=m;i++)
    {
        int x=Find(v[i].x);
        int y=Find(v[i].y);
        if(tati[x]!=tati[y])
        {
            Unire(x,y);
            muchii[++k].x=v[i].x;
            muchii[k].y=v[i].y;
            cost+=v[i].c;
        }
    }
}
void afis()
{
    cout<<cost<<'\n';
    cout<<n-1<<'\n';
    for(int i=1;i<n;i++)
        cout<<muchii[i].x<<" "<<muchii[i].y<<'\n';
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,comp);
    for(int i=1;i<=n;i++)
    {
        tati[i]=i;
        rang[i]=1;
    }
    rez();
    afis();
}