// #include <fstream>
// #include <vector>
// #include <algorithm>
// using namespace std;

// ifstream fin("apm.in");
// ofstream fout("apm.out");

// struct muchie{
//     int x, y, c;
// };

// #define VM vector<muchie>
// #define VI vector<int>

// VM muchii, APM;
// VI repr;
// int n, m;

// bool cmp(muchie u1, muchie u2) {
//     return u1.c < u2.c;
// }

// void Kruskal(int &nodAPM, int &cost) {
//     for (int u = 0; u < muchii.size(); ++u) {
//         if (repr[muchii[u].x] == 0) {
//             repr[muchii[u].x] = muchii[u].x;
//         }
//         if (repr[muchii[u].y] == 0) {
//             repr[muchii[u].y] = muchii[u].y;
//         }
//         if (repr[muchii[u].x] != repr[muchii[u].y]) { // trb reuniti subarborii
//             int subA = repr[muchii[u].x],
//                 subB = repr[muchii[u].y];
//             for (int i = 1; i <= n; ++i) {
//                 if (repr[i] == subB) {
//                     repr[i] = subA;
//                 }
//             }
//             cost += muchii[u].c;
//             ++nodAPM;
//             APM.push_back(muchii[u]);
//         }
//     }
// }

// void printMuchii(VM muc) {
//     for (auto e : muc) {
//         fout << e.x << ' ' << e.y << '\n';
//     }
// }

// int main() { 
//     fin >> n >> m;
//     repr = VI(n + 1, 0);
//     for (int i = 0; i < m; ++i) {
//         muchie u;
//         fin >> u.x >> u.y >> u.c;
//         muchii.push_back(u);
//     }

//     sort(muchii.begin(), muchii.end(), cmp);
//     int cost = 0, nodAPM = 0;
//     Kruskal(nodAPM, cost);
    
//     fout << cost << '\n' << nodAPM  << '\n';
//     printMuchii(APM);
// }
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back

using namespace std;

const int maxn = 400100;

int GR[maxn],X[maxn],Y[maxn],C[maxn];
int N,M,ANS,IND[maxn];
vector<int> VANS;

int grupa(int i)
{
	if (GR[i] == i) return i;
	GR[i] = grupa(GR[i]);
	return GR[i];
}

void reuniune(int i,int j)
{
	GR[grupa(i)] = grupa(j); 
}

bool cmpf(int i,int j)
{
	return(C[i] < C[j]);	
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&N,&M);
	for(int i = 1;i <= M;++i)
	{
		scanf("%d %d %d\n",&X[i],&Y[i],&C[i]);
		IND[i] = i;
	}

	for(int i = 1;i <= N; ++i) GR[i] = i;
	for(int i = 1;i <= N; ++i) GR[i] = i;
	sort(IND + 1,IND + M + 1,cmpf);
	for(int i = 1;i <= M; ++i)
	{
		if (grupa(X[IND[i]]) != grupa(Y[IND[i]])){
			ANS += C[IND[i]];reuniune(X[IND[i]],Y[IND[i]]);
			VANS.pb(IND[i]);
		}
	}
	printf("%d\n",ANS);
	printf("%d\n",N - 1);
	for(int i = 0;i < N - 1; ++i)
		printf("%d %d\n",X[VANS[i]],Y[VANS[i]]);
	return 0;
}