#include <stdio.h>
#include <queue>
#define MMAX 400001
#define NMAX 200001
using namespace std;

typedef struct edge{
    int source, dest, cost; 
          
    bool operator<(edge other) const {
        return cost > other.cost;
    }
     
} edge;

int n, m;
priority_queue<edge> edg;
vector<int> elem[NMAX];
vector<edge> rez_edges;
int rez_sum;
int gr[NMAX];

edge make_edge(int s, int d, int c) {
     edge e;
     e.source = s;
     e.dest = d;
     e.cost = c;
     return e;     
}

void read_() {
     int s, d, c;
     scanf("%d%d", &n, &m);
     for (int i = 0; i < m; i++) {
         scanf("%d%d%d", &s, &d, &c);
         edg.push(make_edge(s, d, c));
     }          
}

int min(int a, int b) {
     return a < b ? a : b;     
}

void change_el(int nod, int root) {
     vector<int>::iterator it;
     for (it = elem[gr[nod]].begin(); it != elem[gr[nod]].end(); it++) {
         elem[gr[root]].push_back(*it);
         if (*it != nod) {
            gr[*it] = gr[root];
         }
     }
     elem[gr[nod]].clear();
     gr[nod] = gr[root];
}

void print_edge(edge e) {
     printf("%d %d %d\n", e.source, e.dest, e.cost);     
}

void print_gr() {
     for (int i = 1; i <= n; i++) {
         printf("%d ", gr[i]);
     }     
     printf("\n\n");
}

void Kruskal() {
     int minR;
     while (edg.size() != 0) {
           edge e = edg.top();
           edg.pop();
           if (gr[e.source] != gr[e.dest]) {
              minR = min(gr[e.source], gr[e.dest]);
              if (gr[e.source] != minR) {
                  change_el(e.source, minR);
              }
              if (gr[e.dest] != minR) {
                  change_el(e.dest, minR);               
              }
              rez_edges.push_back(e);
              rez_sum += e.cost;
              
              //print_edge(e);
              //print_gr();
           }      
     }     
}

void init_() {
     for (int i = 1; i <= n; i++) {
         // La inceput fiecare el este in multimea sa.
         elem[i].push_back(i);
         gr[i] = i;
     }     
}

void print_() {
     vector<edge>::iterator it;
     printf("%d\n%d\n", rez_sum, rez_edges.size());
     for (it = rez_edges.begin(); it != rez_edges.end(); it++) {
         printf("%d %d\n", (*it).source, (*it).dest);
     }     
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    
    read_();
    init_();
    Kruskal();
    print_();
    
    return 0;
}