#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout
int n, m;
struct muchie
{
    int i, j, c;
};
muchie M[400002];
int cc[200002];
int cost, nm, nrm[200001];
void citire()
{
    cin>>n>>m;
    for (int i=1; i<=m; ++i)
        cin>>M[i].i>>M[i].j>>M[i].c;
}
bool comp(muchie a, muchie b)
{
    return a.c<b.c;
}
int Find(int x)
{
    if (cc[x]==0) return x;
    return cc[x]=Find(cc[x]);
}
void kruskal()
{
    sort(M+1, M+m+1, comp);
    for (int i=1; i<=m; ++i)
    {
        int ci=Find(M[i].i);
        int cj=Find(M[i].j);
        if (ci!=cj)
        {
            cc[ci]=cj;
            cost+=M[i].c;
            nrm[++nm]=i;
            if (nm==n-1) break;
        }
    }
}
void afis()
{
    cout<<cost<<'\n';
    cout<<nm<<'\n';
    for (int i=1; i<=nm; ++i)
    {
        int k=nrm[i];
        cout<<M[k].i<<' '<<M[k].j<<'\n';
    }
}
int main()
{
    citire();
    kruskal();
    afis();
    return 0;
}