#include <fstream>
#include <algorithm>
#include <vector>

#define Ndim 200001
#define Mdim 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int DSJ[Ndim];
struct muchie{int c,a,b;}M[Mdim];
vector < pair <int,int> > SOL;
bool cmp(muchie x, muchie y)
{
    return x.c<y.c;
}
int root(int x)
{
    while(DSJ[x]>0)
        x = DSJ[x];
    return x;
}
int main()
{
    int n,m,i,a,b,c,nrm = 0,CostAPM=0,r1,r2;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        M[++nrm].c = c;
        M[nrm].a = a;
        M[nrm].b = b;
    }
    for(i=1;i<=n;i++)
        DSJ[i] = -1;
    sort(M+1,M+nrm+1,cmp);
    for(i=1;i<=m;i++)
    {
        r1 = root(M[i].a);
        r2 = root(M[i].b);
        if(r1!=r2)
        {
            if(DSJ[r1]>DSJ[r2])
                swap(r1,r2);
            DSJ[r1]+=DSJ[r2];
            DSJ[r2] = r1;
            CostAPM += M[i].c;
            SOL.push_back(make_pair(M[i].a,M[i].b));
        }
    }
    fout<<CostAPM<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<SOL[i].first<<' '<<SOL[i].second<<'\n';
    return 0;
}