#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 200005
#define cost first
#define src second.first
#define drn second.second

int n, m;
vector <int> g[MAX_N];
vector <pair <int, pair<int, int> > > e;
vector <pair <int, int> > r;

int h[MAX_N]; // ds heights
int t[MAX_N]; 

int root (int c) {
    while (c != t[c])
          c = t[c];
    return c;
}

int main () {
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    
    scanf ("%d %d", &n, &m);
    
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        scanf ("%d %d %d", &a, &b, &c);
        
        e.push_back (make_pair (c, make_pair (a, b)));
    }
    sort (e.begin(), e.end());
    
    int ct = 0, i = -1, answ = 0;
    
    for (int i = 1; i <= n; ++i) t[i] = i;
    
    while ((ct < n - 1) && (i < m)) {
          ++i;
          int tsrc = root (e[i].src);
          int tdrn = root (e[i].drn);
          if (tsrc == tdrn)
             continue;
          else {
               ++ct;
               answ += e[i].cost;
               r.push_back (make_pair (e[i].src, e[i].drn));
               
               if (h[tsrc] <  h[tdrn]) t[tsrc] = tdrn;
               if (h[tsrc] >  h[tdrn]) t[tdrn] = tsrc;
               if (h[tsrc] == h[tdrn]) {
                           t[tdrn] = tsrc;
                           ++h[tsrc];
               }
          }
    }
    
    printf ("%d\n", answ);
    printf ("%d\n", r.size());
    for (int i = 0; i < r.size(); ++i) printf ("%d %d\n", r[i].first, r[i].second);
    
    return 0;
}