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

using namespace std;

struct edge {
    int x, y, c;

    // pentru sortare crescatoare pe baza de cost
    bool operator<(const edge &right) const {
        return c<=right.c;
    }
};

struct halfEdge {
    int y, c;
};

vector<halfEdge> V[N];
set<edge> S;

int p[N];
int viz[N];
int n, m, rs;

void Prim() {
    viz[1] = 1;

    for (auto edge: V[1]) {
        S.insert({1, edge.y, edge.c});
    }

    for (int i=1; i<n; i++) {
        edge currEdge;

        do {
            currEdge = *S.begin();
            S.erase(S.begin());
        } while (viz[currEdge.y]);

        int x = currEdge.y;
        viz[x] = 1;
        p[x] = currEdge.x;
        rs += currEdge.c;

        for (auto e: V[x]) {
            if (!viz[e.y]) {
                S.insert({x, e.y, e.c});
            }
        }
    }

    while (S.size()) {
        auto c = *S.begin();
        S.erase(S.begin());
    }
}

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;
        V[x].push_back({y, c});
        V[y].push_back({x, c});
    }

    Prim();

    cout<<rs<<" "<<n-1<<'\n';
    for (int i=1; i<=n; i++)
        if (p[i]) cout<<p[i]<<" "<<i<<'\n';

    return 0;
}