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

struct muchie {
   int x, y, c;
};

int dad[200001];
int rang[200001];
muchie mc[400001];
muchie rez[200001];

bool cmp(muchie a, muchie b) {
   return a.c < b.c;
}

int find(int nod) {
    if(dad[nod] == nod) {
        return nod;
    }
    return dad[nod] = find(dad[nod]);
}

void merge(int nod1, int nod2) {
   if(rang[nod1] > rang[nod2]) dad[nod2] = nod1;
   else dad[nod1] = nod2;
   if(rang[nod1] == rang[nod2]) ++rang[nod2];
}

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m, cost = 0, nr = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
      dad[i] = i, rang[i] = 1;
    for(int i = 1; i <= m; ++i)
      cin >> mc[i].x >> mc[i].y >> mc[i].c;
    sort(mc + 1, mc + m + 1, cmp);
    for(int i = 1; i <= m; ++i)
      if(find(mc[i].x) != find(mc[i].y)) {
         merge(find(mc[i].x), find(mc[i].y));
         cost += mc[i].c;
         rez[++nr].x = mc[i].x;
         rez[nr].y = mc[i].y;
         rez[nr].c = mc[i].c;
      }
    cout << cost << '\n' << nr << '\n';
    for(int i = 1; i <= nr; ++i)
      cout << rez[i].x << ' ' << rez[i].y << '\n';
    return 0;
}