// O(m log n)
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define N 200001
using namespace std;

struct nod {
    int u, c;
    nod(){};
    nod(int _u, int _c) { u = _u; c = _c; };
};

vector<nod> a[N];
int minEdge[N];
int parent[N];
bool inMST[N];
int n, m;

struct cmp {
    bool operator()(const int &a, const int &b) const {
        return minEdge[a] > minEdge[b];
    };
};

bool inQueue[N];
void prim() {
    priority_queue<int, vector<int>, cmp> Q;

    int sol = 0;
    vector<pair<int, int> > solution;
    int i;
    memset (minEdge, 0x3f3f3f3f, sizeof(minEdge));
    minEdge[1] = 0;
    
    for (i = 1; i <= n; ++i)
        Q.push(i);
    inQueue[1] = true;
    
    while (!Q.empty()) {
        int u = Q.top();
        Q.pop();
        inQueue[u] = false;
        
        if (inMST[u] == true)
            continue;
        inMST[u] = true;

        if (parent[u]) {
            solution.push_back(make_pair(u, parent[u]));
            sol += minEdge[u];
        }
        
        for (vector<nod>::iterator it = a[u].begin(); it != a[u].end(); ++it)
            if (!inMST[it->u] && it->c < minEdge[it->u]) {
                parent[it->u] = u;
                minEdge[it->u] = it->c;
                //if (!inQueue[it->u]) {
                    Q.push(it->u);
                 //   inQueue[it->u] = true;
               // }
            }
    }
    /*
    for (i = 1; i <= n; ++i)
        if (parent[i]) {
            solution.push_back(make_pair(i, parent[i]));
            sol += minEdge[i];
        }
    */
    printf ("%d\n", sol);
    printf ("%d\n", solution.size());
    for (int i = 0; i < solution.size(); ++i)
        printf ("%d %d\n", solution[i].first, solution[i].second);
}

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


    scanf ("%d %d", &n, &m);
    int p, q, c;
    while (m--) {
        scanf ("%d %d %d", &p, &q, &c);
        a[p].push_back( nod(q, c) );
        a[q].push_back( nod(p, c) );
    }
    
    prim();
}