// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;

#define NMAX        200009
#define MMAX        400009
#define kInf        (1 << 30)
#define kInfLL      (1LL << 60)
#define kMod        666013

#define USE_FILES "MLC"

#ifdef USE_FILES
#define cin fin
#define cout fout
ifstream fin("apm.in");
ofstream fout("apm.out");
#endif

// number of tests from "in"
int test_cnt = 1;
void clean_test();

struct edge {
    int x, y, cost;
} edges[MMAX];

// your global variables are here
int N, M, x, y, cost, cnt;
int dad[NMAX], rang[NMAX];
long long totalCost;
vector <int> sol;
 
int findDad(int node) {
    if (dad[node] != node) {
        dad[node] = findDad(dad[node]);
    }
     
    return dad[node];
}
 
void unite(int x, int y) {
    int px = findDad(x);
    int py = findDad(y);
     
    if (rang[px] < rang[py]) {
        dad[px] = py;
        rang[px] += rang[py];
    } else {
        dad[py] = px;
        rang[py] += rang[px];
    }
}

// your solution is here
void solve() {
    cin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        cin >> edges[i].x >> edges[i].y >> edges[i].cost;
    }
    
    for (int i = 1; i <= N; ++i) {
        dad[i] = i;
        rang[i] = 1;
    }
    
    sort(edges + 1, edges + M + 1, [](const edge &e1, const edge &e2) {
       return (e1.cost < e2.cost); 
    });
    
    for (int i = 1; i <= M && cnt < N - 1; ++i) {
        if (findDad(edges[i].x) != findDad(edges[i].y)) {
            unite(edges[i].x, edges[i].y);
            totalCost += edges[i].cost;
            sol.push_back(i);
            ++cnt;
        }
    }
    
    cout << totalCost << '\n' << N - 1 << '\n';
    for (auto &i : sol) {
        cout << edges[i].x << ' ' << edges[i].y << '\n';
    }

    if (test_cnt > 0) {
        clean_test();
    }
}


void clean_test() {
    // clean if needed
}

int main() {
//     cin >> test_cnt;
    while (test_cnt--) {
        solve();
    }

    return 0;
}