#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

#define MAXM 400020
#define MAXN 200020

int dad[MAXN];

struct str{
    int x,y,c;
}a[MAXM],b[MAXM];

inline bool cmp(str h, str b)
{
    return h.c<b.c;
}

int sef(int x)
{
    if(dad[x]!=x)
        dad[x]=sef(dad[x]);
    return dad[x];
}

int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=n;i++)
        dad[i]=i;
    int h=0,c=0;
    for(int i=1;i<=m;i++)
    {
        int x=sef(a[i].x);
        int y=sef(a[i].y);
        if(x!=y)
        {
            c+=a[i].c;
            dad[x]=y;
            b[++h].x=a[i].x;
            b[h].y=a[i].y;
        }
    }
    fout<<c<<"\n"<<h<<"\n";
    for(int i=1;i<=h;i++)
        fout<<b[i].x<<" "<<b[i].y<<"\n";
    return 0;
}