#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define c first
#define m1 second.first
#define m2 second.second
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector< pair<int,pair<int,int> > > v;
vector<pair<int,int> > sol;
int N,M,i,j,c,x,y,P[200001],a,b,sum;

int fi(int x)
{
    if (P[x]==x)
        return x;
    P[x]=fi(P[x]);
    return P[x];
}
void u(int a,int b){P[fi(a)]=P[fi(b)];}

int main()
{

    f>>N>>M;
    for (i=1;i<=N;++i)P[i]=i;
    for (i=1;i<=M;++i)
    {
        f>>x>>y>>c;
        v.push_back(make_pair(c,make_pair(y,x)));
    }
    sort(v.begin(),v.end());
    for(i=0;i<M;++i)
    {
        if (fi(v[i].m1)!=fi(v[i].m2))
        {
            u(v[i].m1,v[i].m2);
            sum+=v[i].c;
            sol.push_back(make_pair(v[i].m1,v[i].m2));
        }
    }
    g<<sum<<'\n'<<N-1<<'\n';
    for (i=0;i<sol.size();++i)
        g<<sol[i].first<<" "<<sol[i].second<<'\n';

    return 0;
}