#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
// vector<vector<pair<int,int>>> adj;
vector<tuple<int,int,int>> edges;

struct DSU{
    vector<int> root;
    vector<int> rang;
    DSU(int n){
        root.resize(n+1);
        rang.resize(n+1, 0);
        for(int i = 1; i<=n; i++){
            root[i] = i;
        }
    }
    int find(int x){
        int parent = root[x];
        if(root[parent] != parent) return root[x] = find(parent);
        return parent;
    }
    void unite(int x, int y){
        int rx = find(x), ry = find(y);
        if(rx == ry) return;
        if(rang[rx] < rang[ry]){
            swap(rx, ry);
        }
        root[ry] = rx;
        if(rang[ry] == rang[rx])rang[rx]++;
    }

};

void citire(){
    fin >> n >> m;
    // adj.resize(n+1);
    while(m--){
        int x,y,c;
        fin >> x >> y >> c;
        edges.push_back({x,y,c});
    }
}

bool comp(tuple<int,int,int> a, tuple<int,int,int> b){
    return get<2>(a) <= get<2>(b);
}

void apm(){
    int cost = 0, cnt = 0;
    DSU dsu(n);
    vector<pair<int,int>> v;
    sort(edges.begin(),edges.end(), comp);
    for(auto [x,y,c] : edges){
        if(dsu.find(x) != dsu.find(y)){
            cost += c;
            v.push_back({x,y});
            dsu.unite(x,y);
            if(++cnt == n-1) break;
        }
    }
    fout << cost << '\n';
    fout << cnt << '\n';
    for(auto e : v){
        fout << e.first << ' ' << e.second << '\n'; 
    }
}

int main(){
    citire();
    apm();

    return 0;
}