#include<bits/stdc++.h>
#define N 200030
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
#define dim 50001
char buff[dim];
int pos = 0;

void read (int &nr) {
	nr = 0;
	while ((buff[pos] < '0' || buff[pos] > '9') && buff[pos] != '-')
		if (++pos == dim)
			fread(buff, 1, dim, stdin), pos = 0;
	int semn = 1;
	if (buff[pos] == '-') {
		semn = -1;
		if (++pos == dim)
			fread(buff, 1, dim, stdin), pos = 0;
	}
	while (buff[pos] >= '0' && buff[pos] <= '9') {
		nr = 10 * nr + buff[pos] - '0';
		if (++pos == dim)
			fread(buff, 1, dim, stdin), pos = 0;
	}
	nr *= semn;
}
struct lol {
    int x, y,c;
    bool operator<(const lol &other) const {
        return c<other.c;
    }
};

int n,m,rs,k;
bool inA[N];
vector<pii>V[N];
int p[N];
set<lol>S;

void Prim() {
    inA[1]=1;
    for (auto it:V[1]) {
        S.insert({1,it.x,it.y});
    }
    for (int i=1; i<n; ++i) {
        lol top;
        do {
            top=*S.begin();
            S.erase(S.begin());
        } while (inA[top.y]);
        int x=top.y;
        inA[x]=1;
        p[x]=top.x;
        rs+=top.c;
        for (auto it:V[x]) {
            if (!inA[it.x]) {
                S.insert({x,it.x,it.y});
            }
        }
    }
}

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read(n); read(m);
    for (int i=1; i<=m; ++i) {
        int x,y,c; read(x); read(y); read(c);
        V[x].push_back({y,c});
        V[y].push_back({x,c});
    }
    Prim();
    cout<<rs<<'\n'<<n-1<<'\n';
    for (int i=1; i<=n; ++i) {
        if (p[i]) cout<<p[i]<<" "<<i<<'\n';
    }

    return 0;
}