#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,tata[200001],cnt,Rang[200001],s;
struct pereche
{
    int a,b,cost;
} x[400001],y[400001];
bool cmp(pereche a,pereche b)
{
    return a.cost<b.cost;
}
int Radacina(int k)
{
    while(tata[k]!=k)
        k=tata[k];
    return k;
}
void Compresie(int p,int q)
{
    int r=p,s=q;
        if(Rang[r]>Rang[s])
            tata[s]=r;
        else
        {
            tata[r]=s;
            if(Rang[r]==Rang[s])
                Rang[r]++;
        }
    }
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>x[i].a>>x[i].b>>x[i].cost;
    sort(x+1,x+m+1,cmp);
    for(int i=1; i<=n; i++)
        tata[i]=i;
    for(int i=1; i<=m; i++)
    {
        if(Radacina(x[i].a)!=Radacina(x[i].b))
        {
            s+=x[i].cost;
            Compresie(Radacina(x[i].a),Radacina(x[i].b));
            cnt++;
            y[cnt].a=x[i].a,y[cnt].b=x[i].b;
        }
    }
    fout<<s<<'\n'<<cnt<<'\n';
    for(int i=1; i<=cnt; i++)
        fout<<y[i].a<<' '<<y[i].b<<'\n';
    return 0;
}