#include <bits/stdc++.h>

using namespace std;

#if 1
    #define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
    #define pn cout<<endl
#else
    #define pv(x)
    #define pn
#endif

#ifdef ONLINE_JUDGE
    #define in cin
    #define out cout
#else
    ifstream in("apm.in");
    ofstream out("apm.out");
#endif

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 1e5 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;

int N,M,height,root;
int dad[NMax], nr[NMax];

struct elem {
    int x,y,c;
    bool used;
}edg[NMax];

bool operator<(elem a,elem b) {
    return a.c < b.c;
}

int findRoot(int node) {
    if (dad[node] == node) {
        return node;
    }

    int root = findRoot(dad[node]);
    dad[node] = root;
    return root;
}

void unite(int r1,int r2) {
    if (nr[r1] > nr[r2]) {
        dad[r2] = r1;
        nr[r1] += nr[r2];
    }
    else {
        dad[r1] = r2;
        nr[r2] += nr[r1];
    }
}

int main() {
    in>>N>>M;
    for (int i = 1;i <= M;++i) {
        in >> edg[i].x >> edg[i].y >> edg[i].c;
    }

    for (int i = 1;i <= N;++i) {
        dad[i] = i;
        nr[i] = 1;
    }

    sort(edg+1, edg+M+1);

    int cost = 0;
    for (int i = 1;i <= M;++i) {
        int rootX = findRoot(edg[i].x), rootY = findRoot(edg[i].y);

        if (rootX == rootY) {
            continue;
        }

        cost += edg[i].c;
        unite(rootX,rootY);
        edg[i].used = true;
    }

    out << cost << '\n' << N-1 << '\n';
    for (int i = 1;i <= M;++i) {
        if (edg[i].used) {
            out << edg[i].x << ' ' << edg[i].y << '\n';
        }
    }

    return 0;
}