#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

const int maxm = 4e5 + 5, maxn = 2e5 + 5;

struct much  {
    int x, y, c;
};

much v[maxm];

bool cmp(much a, much b)  {
    return a.c < b.c;
}

int tata[maxn];

inline int find1(int nod)  {
    int backup = nod;
    while(nod != tata[nod])
        nod = tata[nod];
    while(backup != nod)  {
        int aux;
        aux = tata[backup];
        tata[backup] = nod;
        backup = aux;
    }
    return nod;
}

inline int union1(int x, int y)  {
    tata[find1(x)] = find1(y);
}

#define a first
#define b second

int bst = 0;
vector <pair <int, int> > ans;

int main()  {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
	int n, m;
	cin >> n >> m;
	for(int i = 1;i <= m;i++)  {
        cin >> v[i].x >> v[i].y >> v[i].c;
	}
	sort(v + 1, v + m + 1, cmp);
    for(int i = 1;i <= n;i++)
        tata[i] = i;
	for(int i = 1;i <= m;i++)  {
        int x, y, c;
        x = v[i].x, y = v[i].y, c = v[i].c;
        if(find1(x) != find1(y))  {
            union1(x, y);
            bst += c;
            ans.push_back({x, y});
        }
	}
	cout << bst << "\n";
	cout << n - 1 << "\n";
	for(int i = 0;i < n - 1;i++)
        cout << ans[i].a << " " << ans[i].b << "\n";
	return 0;
}