#include <iostream>
#include <vector>
#include<stdio.h>
#include <algorithm>
using namespace std;
const  int maxn = 400009;

int grup[maxn],X[maxn],Y[maxn],cost[maxn], n,m,suma,ordine[maxn];
vector<int> rez;

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

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

bool cmpf(int i,int j)
{
return(cost[i] < cost[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],&cost[i]);
ordine[i] = i;
}
for(int i = 1;i <= n; ++i) grup[i] = i;
sort(ordine + 1,ordine + m + 1,cmpf);

for(int i = 1;i <= m; ++i)
    {
    if (grupa(X[ordine[i]]) != grupa(Y[ordine[i]])){
    suma += cost[ordine[i]];
    reuniune(X[ordine[i]],Y[ordine[i]]);
    rez.push_back(ordine[i]);
    }
}
printf("%d\n",suma);
printf("%d\n",n - 1);
for(int i = 0;i < n - 1; ++i)
    printf("%d %d\n",X[rez[i]],Y[rez[i]]);
return 0;
}