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

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

struct adat
{
    int cs1,cs2;
    int k;
};
vector <adat> x;
vector <int> v;
vector <pair<int,int> > y;
int n,m,i,j,c,p,q,sum,a,b,db;

int has (adat a, adat b)
{
    return a.k<b.k;
}
int main()
{
    cin>>n>>m;
    x.resize(m+1);
    v.resize(n+1);
    for (i=0;i<m;++i)
    {
        cin>>x[i].cs1>>x[i].cs2>>x[i].k;
    }

    for (i=1;i<=n;++i) v[i]=i;

    sort (x.begin(),x.end(),has);


   // for (i=0;i<m;++i) cout<<x[i].k<<" "<<x[i].cs1<<" "<<x[i].cs2<<"\n";
    db=0;
    for (i=0;i<m;++i)
    {
        a=x[i].cs1;
        b=x[i].cs2;
        c=x[i].k;
        p=v[a];
        q=v[b];
        if (p!=q)
        {
            y.push_back({a,b});
            sum+=c;
            for (j=1;j<=n;++j)
            {
                if (v[j]==q) v[j]=p;
            }
            db++;
        }
        if (db==n-1) break;
    }

    cout<<sum<<"\n"<<db<<"\n";
    for (auto e:y) cout<<e.first<<" "<<e.second<<"\n";
    return 0;
}