#include <bits/stdc++.h>

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

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 2e5 + 5;
const int MMax = 4e5 + 5;
const int inf = 1e9 + 5;
using zint = int;

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

struct muchie {
    int x,y,c;
}m[MMax];
vector<muchie> apmEdges;

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

int findRoot(int);
void unite(int,int);

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

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

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

    int costTotal = 0;
    for (int i = 1;i <= M;++i) {
        //pv(m[i].x);pv(m[i].y);pv(m[i].c);pn;

        int x = m[i].x, y = m[i].y;
        int rootX = findRoot(x), rootY = findRoot(y);
        if (rootX == rootY) {
            continue;
        }

        unite(rootX,rootY);
        apmEdges.pb(m[i]);
        costTotal += m[i].c;
    }

    out<<costTotal<<'\n'<<N-1<<'\n';
    for (auto elem : apmEdges) {
        out<<elem.x<<' '<<elem.y<<'\n';
    }

    in.close();out.close();
    return 0;
}

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[r1] = r2;
        nr[r2] += nr[r1];
    }
    else {
        dad[r2] = r1;
        nr[r1] += nr[r2];
    }
}