#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define maxn 100001
int tata[maxn], rang[maxn];
int n, m;

int root(int x) {
    vector<int> v;
    if (x == tata[x]) return x;
    else {
        while (tata[x] != x) {
            v.push_back(x);
            tata[x] = tata[tata[x]];
            x = tata[x];
        }
        for (auto nod: v)
            tata[nod] = x;

        return x;
    }
}

void unire(int x, int y) {
    int r1 = root(x);
    int r2 = root(y);
    if (rang[r1] <= rang[r2]) {
        tata[r1] = r2;
        rang[r2] += rang[r1];
    } else {
        tata[r2] = r1;
        rang[r1] += rang[r2];
    }
}struct Comp{
    bool operator()(vector<int> v1,vector<int> v2)
    {
        return v1[2]<v2[2];
    }
};
int main() {
    int cost, x, y;
    f >> n >> m;

    vector<vector<pair<int,int>>>lista;
    for(int i = 0;i<n+1;i++)
        lista.push_back({});
    vector<vector<int>> muchii;
    for (int i = 0; i < m; i++) {
       f>>x>>y>>cost;
       muchii.push_back({x,y,cost});
       lista[x].push_back({y,cost});
       lista[y].push_back({x,cost});
    }
    sort(muchii.begin(),muchii.end(),Comp());
    for (int i = 1; i <= n; i++) {
        tata[i] = i;
        rang[i] = 1;
    }
    set<int> apm;
    int costTotal = 0;
    int nrMuchii = 0;
    int count = 0;
    vector<pair<int,int>> muchiiSelectate;
    while (nrMuchii<n-1)
    {
        vector<int> muchie = muchii[count++];
        if(root(muchie[0]) != root(muchie[1]))
        {
            unire(muchie[0],muchie[1]);
            costTotal += muchie[2];
            nrMuchii ++;
            apm.insert(muchie[0]);
            apm.insert(muchie[1]);
            muchiiSelectate.push_back({muchie[0],muchie[1]});
        }

    }
    g<<costTotal<<'\n';
    g<<nrMuchii<<'\n';
    for(int i  = 0;i<muchiiSelectate.size();i++)
        g<<muchiiSelectate[i].first<<' '<<muchiiSelectate[i].second<<'\n';
    f.close();
    g.close();
    return 0;
}