#include <fstream>
#include <vector>
#include <algorithm>
#define st second.first
#define dr second.second
#define cost first

using namespace std;

pair <int , pair <int , int>> l[2000001];
int n,i,m,rx,ry,s,k=-1;
ifstream f("APM.in");
ofstream g("APM.out");

int t[400001];

int rad(int x){
    while(t[x]>0)
        x = t[x];
    return x;}

int main()
{
    f >> n >> m; int P[m],u[m];
    for(i=0;i<=m;i++) t[i]=-1;

    for(i=0;i<m;i++)
    f >> l[i].st>>l[i].dr>>l[i].cost;
    sort (l,l+m);

    for(i=0;i<m;i++){

        rx = rad(l[i].st);
        ry = rad(l[i].dr);

        if(rx!=ry){

                s+=l[i].cost;
                P[++k]=l[i].st;
                u[k]=l[i].dr;

            if(t[rx]<t[ry]){
                t[rx]+=t[ry];
                t[ry]=rx;}

            else {
                t[ry]+=t[rx];
                t[rx]=ry;}
                }
            }

            g << s << "\n" << k << "\n";

        for(i=0;i<=k;i++)
            g << P[i] << " " << u[i] << "\n";


    return 0;
}