#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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


struct Edge
{
    int x,y,cost;
};

int GR[200001],h[200001],N,M,Cost;
vector<Edge> edges;
vector<Edge> ANS;

int group(int i)
{
    while(GR[i]!=0)
        i=GR[i];
    return i;
}

void Union(int i, int j)
{
    if(h[i]>h[j])
        GR[j]=i;
    else
    {
        GR[i]=j;
        if(h[i]==h[j])
            h[j]++;
    }
}
 void kruskal()
 {
    sort(edges.begin(),edges.end(),[](Edge a, Edge b){return a.cost<b.cost;});
    for(auto e : edges)
    {
        int rootx=group(e.x),rooty=group(e.y);
        if((rootx==0&&rooty==0)||(rootx!=rooty))
        {
            Union(rootx,rooty);
            Cost += e.cost;
            ANS.push_back(e);
        }
    }

 }
int main()
{
    in>>N>>M;
    while(M)
    {

        Edge E;
        in>>E.x>>E.y>>E.cost;
        edges.push_back(E);
        M--;
    }
    kruskal();
    out<<Cost<<"\n";
    out<<ANS.size()<<"\n";
    for(auto a: ANS)
    {
        out<<a.y<<" "<<a.x<<"\n";
    }
    return 0;

}