//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");

struct adat
{
    int a,b,k;
    bool ok;
};
vector <adat> x;
vector <int> y;
int n,m,i,j,a,p,b,q;
int has (adat a, adat b)
{
    if (a.k<b.k) return 1;
    else return 0;
}
int main()
{
    cin>>n>>m;
    x.resize(m+1);
    y.resize(n+1);
    for (i=1;i<=m;++i)
    {
        cin>>x[i].a>>x[i].b>>x[i].k;
        x[i].ok=false;
    }

    sort (x.begin()+1,x.end(),has);
    for (i=1;i<=n;++i) y[i]=i;

    int sum=0,db=0;
    for (i=1;i<=m;++i)
    {
        a=x[i].a;
        b=x[i].b;
        p=y[a];
        q=y[b];
        if (p!=q)
        {
            sum+=x[i].k;
            x[i].ok=true;
            for (j=1;j<=n;++j)
            {
                if (y[j]==p) y[j]=q;
            }
            db++;
        }
        if (db==n-1) break;
    }

    cout<<sum<<"\n"<<db<<"\n";

    for (i=1;i<=m;++i) if (x[i].ok) cout<<x[i].a<<" "<<x[i].b<<"\n";
    return 0;
}