#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct mazan
{
    int a,b,c;
};
mazan v[400001];
int tata[200001],sum,cnt;
pair <int,int> afis[200001];
int radacina(int val)
{
    if(tata[val]==0)
        return val;
    tata[val]=radacina(tata[val]);
    return tata[val];
}
bool cmp(mazan a,mazan 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;
    sum+=c;
    tata[ry]=rx;
    afis[++cnt].first=a;
    afis[cnt].second=b;
}
int main()
{
    int n,m,i;
    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<<sum<<'\n'<<n-1<<'\n';
    for(i=1; i<=cnt; i++)
        out<<afis[i].first<<" "<<afis[i].second<<'\n';
    return 0;
}