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

#define NMAX 400001
#define MMAX 200001
int n,m,i;
struct edge
{
    int a,b,c;
};
edge v[NMAX];
int tata[MMAX],total,quant;
pair <int,int> afis[MMAX];
int radacina(int val)
{
    if(tata[val]==0)
        return val;
    tata[val]=radacina(tata[val]);
    return tata[val];
}

bool cmp(edge a,edge b)
{
    if(a.c<b.c)
        return 1;
    return 0;
}

void reuniune(int a,int b,int c)
{
    int rx=radacina(a),ry=radacina(b);
    if(rx==ry)
        return;
    total+=c;
    tata[ry]=rx;
    afis[++quant].first=a;
    afis[quant].second=b;
}
int main()
{

    in>>n>>m;
    for(i=1; i<=m; i++)
        in>>v[i].a>>v[i].b>>v[i].c;
    sort(v+1,v+m+1,cmp);
     for(i=1; i<=m; i++)
        reuniune(v[i].a,v[i].b,v[i].c);
    out<<total<<'\n'<<n-1<<'\n';
    for(i=1; i<=quant; i++)
        out<<afis[i].second<<" "<<afis[i].first<<'\n';
    return 0;
}