#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

#define NMAX 400001

int n, m, TT[NMAX], RG[NMAX], k=0, total;

struct muchie{int x, y, cost;} v[NMAX];
pair <int, int> p[NMAX];

bool compara(muchie a, muchie b)
{
    return a.cost<b.cost;
}

int Find(int nod)
{
    while(TT[nod]!=nod)
        nod=TT[nod];
    return nod;
}

void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
    fin>>v[i].x>>v[i].y>>v[i].cost;
    TT[i]=i;
    RG[i]=1;
    }
    sort(v+1, v+m+1, compara);
}
void uneste(int x, int y)
{
     if(RG[x]<RG[y])
     {
     TT[x]=y;
     }
     if(RG[x]>RG[y])
     {
     TT[y]=x;
     }
     if(RG[x]==RG[y])
     {
     TT[x]=y;
     RG[y]++;
     }
}

void rezolva()
{
     for(int i=1; i<=m; i++)
     {
     int fx, fy;
     fx=Find(v[i].x);
     fy=Find(v[i].y);
     if(fx!=fy)
     {
     uneste(fx, fy);
     k++;
     p[k].first=v[i].x;
     p[k].second=v[i].y;
     total+=v[i].cost;
     }
     }
}

void afis()
{
    fout<<total<<'\n';
    fout<<n-1<<'\n';
    for(int i=1; i<=k; i++)
    {
    fout<<p[i].first<<" "<<p[i].second<<'\n';
    }
}

int main()
{
    citire();
    rezolva();
    afis();
    return 0;
}