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

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

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

Muchie graph[400001];
int n,m,k;
int Total,TN[400001], RN[400001];
pair<int,int> P[400001];
   bool Compare(Muchie a, Muchie b){
    return a.cost < b.cost;
    }
void Read(){
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>graph[i].x;
        in>>graph[i].y;
        in>>graph[i].cost;
    }
    sort(graph+1, graph+m+1,Compare);

}

int TataNod(int nod){
    while(nod != TN[nod])
    nod = TN[nod];

    return nod;
}
void Unire(int x,int y){
   if(x==y){
    TN[y] = x;
    RN[x] ++;
    return;
   }
   if(RN[x]<RN[y]){
    TN[x] = y;
    return;
   }
   TN[y] = x;
}
void Rezolvare(){
    for(int i=1;i<=m;i++){
        int nodX = TataNod(graph[i].x);
        int nodY = TataNod(graph[i].y);
        if(nodX != nodY){
            Unire(nodX,nodY);
            P[++k].first = graph[i].y;
            P[k].second = graph[i].x;
            Total += graph[i].cost;

        }
    }
}
int main()
{
    k=0;
    Total = 0;
Read();
for(int i=1;i<=n;i++){
    RN[i] = 1;
    TN[i] = i;
}
Rezolvare();

out<<Total<<"\n";
out<<k<<"\n";
for(int i=1;i<=k;i++){
    out<<P[i].first<<" "<<P[i].second<<"\n";
}
}