#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define maxn 400100
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int gr[maxn], Xc[maxn], Yc[maxn], C[maxn];
int n,m, ANS, ind[maxn];
vector <int> VANS;
void read()
{
    in>>n>>m;
    int i;
    for(i=1;i<=m;++i)
    {
        in>>Xc[i]>>Yc[i]>>C[i];
        ind[i]=i;
    }
}
void init()
{
    int i;
    for(i=1;i<=n;i++)
        gr[i]=i;
}
int grupa(int i)
{
    if(gr[i]==i) return i;
    gr[i]=grupa(gr[i]);
    return gr[i];
}
void reuniune(int i, int j)
{
    gr[grupa(i)]=grupa(j);
}
bool gDo(int i, int j)
{
    return(C[i]<C[j]);
}
void kruscal()
{
    sort(ind+1,ind+m+1,gDo);
    int i;
    for(i=1;i<=m;++i)
        if(grupa(Xc[ind[i]])!=grupa(Yc[ind[i]]))
        {
            ANS+=C[ind[i]];
            reuniune(Xc[ind[i]], Yc[ind[i]]);
            VANS.push_back(ind[i]);
        }
    out<<ANS<<endl;
    out<<n-1<<endl;
    for(i=0;i<n-1;++i)
    {
        out<<Yc[VANS[i]]<<" "<<Xc[VANS[i]]<<endl;
    }
}
int main()
{
    read();
    init();
    kruscal();
    return 0;
}