#include <stdio.h>
#include <stdlib.h>
#define NMAX 400100	
	
	
int ANS[NMAX];
int solSize = 0;
int X[NMAX], Y[NMAX], IND[NMAX], FATHER[NMAX], N, M, COST[NMAX];
	
int COST_SOL = 0;
	
int find_(int x) {
	
   if(FATHER[x] == x) return x;
   FATHER[x] = find_(FATHER[x]);
   return FATHER[x];
}
	
void unite_(int x, int y) {
    FATHER[find_(y)] = find_(x);
}
	
 
int cmp(int x, int y) {
	if(COST[x] <= COST[y]){
        return 1;
    }
    return -1;
	
}

void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
  
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];   
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (cmp(arr[j], pivot) == 1) 
        { 
            i++;    
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
  
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    {     
        int pi = partition(arr, low, high); 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
 
	
void read() {
	
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=M; i++) {
	
        scanf("%d%d%d", &X[i], &Y[i], &COST[i]);
	
        IND[i] = i;
	
    }
    quickSort(IND, 1, M + 1);	
    for(int i = 1; i<=N; i++){
        FATHER[i] = i;
    }
	
}
	
void solve() {
	
    for(int i = 1; i<=M; i++) {
        if(find_(X[IND[i]]) != find_(Y[IND[i]])){
            COST_SOL += COST[IND[i]];
            ANS[++solSize] = IND[i];
            unite_(X[IND[i]], Y[IND[i]]);
	
        }
	
    }
	
}
	
 
	
void write() {
	
    printf("%d\n", COST_SOL);
    printf("%d\n", solSize);
	
 
	
    for(int i = 1; i<=solSize; i++) {
        printf("%d %d\n", X[ANS[i]], Y[ANS[i]]);
    }
	
}
	
int main() {
		
    FILE *f = freopen("apm.in", "r", stdin);
    FILE *g = freopen("apm.out", "w", stdout);

    read();
    solve();
    write();
	
    return 0;
	
}