#include<bits/stdc++.h>
#define N 1000005

using namespace std;

struct edge {
    int x, y, c;

    bool operator<(const edge &right) const {
        return c < right.c;
    }
} M[N];

int n, m, totalCost;
int p[N];


bool cmp(edge l, edge r) {
    return (l.c<r.c);
}

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

void unite(int a, int b) {
    p[find(a)] = find(b);
}

void Kruskal() {
    for (int i=1; i<=n; i++) p[i]=i;

    sort(M+1, M+m+1); // number of edges in the current MST
    int k = 0;

    for (int i=1; i<=m; i++) {
        int a = M[i].x;
        int b = M[i].y;
        int c = M[i].c;

        if (find(a) != find(b)) {
            unite(a, b);

            totalCost += c;
            M[++k] = M[i];
        }
    }
}


int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    cin>>n>>m;

    for (int i=1; i<=m; i++) {
        int x,y,c; cin>>x>>y>>c;
        M[i] = {x, y, c};
    }

    Kruskal();

    cout<<totalCost<<" "<<n-1<<'\n';
    for (int i=1; i<n; i++) cout<<M[i].x<<" "<<M[i].y<<'\n';

    return 0;
}