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

vector<int> adj[100];
vector<pair<int, int>> muchii;
int p[1000], h[1000];

void init(int n){
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        h[i] = 0;
    }
}

int find(int x){
    while(x!=p[x]){
        x=p[x];
    }
    return x;
}

void unire(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    
    if(h[x] < h[y]){ 
        p[x] = y;
    } else {
        if(h[x] > h[y]){
            p[y] = x;
        } else { 
            p[x] = y;
            h[y]++;
        }
}
}



int main(){
    int n, m, sol=0, x, y, c, nr=0;
    ifstream f("apm.in");
    f>>n>>m;
    for(int i=0; i<m; i++){
        f>>x>>y>>c;
        if(find(x)!=find(y)){
            sol=sol+c;
            adj[x].push_back(y);
            adj[y].push_back(x); 
            muchii.push_back({x,y}); 
            nr++;
            unire(x, y);
        }
    }
    f.close();
    
    ofstream g("apm.out");
    g<<sol<<endl;
    g<<nr<<endl;
    for(auto edge : muchii){
        g<<edge.first<<" "<<edge.second<<endl;
    }
    return 0;
}