#include <cstdio>
#include <algorithm>

using namespace std;

struct muchie {
    int x, y, c;
};
muchie M[400001];
int CC[200001], nrM[200001],
    n, m, cost;
bool cmp(const muchie &a, const muchie &b) {
    return a.c < b.c;
}
/*class cmp {
    public:
        bool operator()(const muchie &a, const muchie &b) {
            return a.c < b.c;
        }
};*/

int find_c(int x) {
    return (CC[x] == x) ? x : CC[x] = find_c(CC[x]);
}

void Kruskal() {
    sort(M+1, M+m+1, cmp);
    for(int i = 1; i <= n; i++)
        CC[i] = i;
    int nm = 0;
    for(int i = 1; i <= m; i++) {
        int pI = find_c(M[i].x),
            pJ = find_c(M[i].y);
        if(pI != pJ) {
            cost += M[i].c;
            CC[pI] = pJ;
            nrM[++nm] = i;
            if(nm == n-1) break;
        }
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%i %i", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%i %i %i", &M[i].x, &M[i].y, &M[i].c);
    Kruskal();

    printf("%i\n%i\n", cost, n-1);
    for(int i = 1; i < n; i++)
        printf("%i %i\n", M[nrM[i]].x, M[nrM[i]].y);
    return 0;
}