#include <bits/stdc++.h>
#define MAXN 100000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector< pair<int, int> > g;//graph
struct edgeInArray{
    int x, y, c;
}a[2*MAXN];
int find(int i, int sefi[]){
    if(sefi[i]==i)//if it's the CEO
      return sefi[i];//return the guy
    else
      return sefi[i]=find(sefi[i], sefi);//find the boss' boss
      //Path  Compression is easier than ranks
}
void unify(int i, int j, int sefi[]){//unify two trees
    int sef_i=find(i, sefi), sef_j=find(j, sefi);
    sefi[sef_j]=sef_i;
}
int kruskalTree(int e, int n){
    int sefi[MAXN], edgesAdded=0, cost=0;
    for(int i=0; i<n; i++)
        sefi[i]=i;//so far, n trees, n sets
    for(int i=0; i<e; i++){//go through the edges
        if(find(a[i].x, sefi)!=find(a[i].y, sefi)){//if endpoints are not in same set
             unify(a[i].x, a[i].y, sefi);//this changes sefi[i] so find actually works
             cost+=a[i].c;
             g.push_back(make_pair(a[i].x, a[i].y));
        }
    }
    return  cost;
}
bool compareTwoEdges(edgeInArray a, edgeInArray b){
    return a.c<b.c;
}
int main()
{
    int n, e; fin>>n>>e;//nodes & edges
    for(int i=0; i<e; i++){
        fin>>a[i].x>>a[i].y>>a[i].c;
        /*g[a[i].x].push_back(make_pair(a[i].y, a[i].c));
        g[a[i].y].push_back(make_pair(a[i].x, a[i].c));*/
    }
    sort(a, a+e, compareTwoEdges);
    fout<<kruskalTree(e, n)<<"\n";
    fout<<g.size()<<"\n";
    for(int i=0; i<g.size(); i++){
        fout<<g[i].first<<" "<<g[i].second<<"\n";
    }
    return 0;
}