#include <cstdio>
#include <vector>
#define maxn 400100
#include <algorithm>
using namespace std;
vector<int> VANS;
int X[maxn], Y[maxn], C[maxn], IND[maxn], GR[maxn];
int n, m, ANS;
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]);
}
void citire()
{
    int i;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d", &X[i], &Y[i], &C[i]);
        IND[i]=i;
    }
    for(i=1;i<=n;++i)
        GR[i]=i;
    sort(IND+1, IND+m+1, cmpf);
}
void afisare()
{
    int i;
    printf("%d\n%d\n", ANS, n-1);
    for(i=0;i<n-1;++i)
        printf("%d %d\n", X[VANS[i]], Y[VANS[i]]);
}
void rezolva_problema()
{
    int i;
    citire();
    for(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.push_back(IND[i]);
        }
    }
    afisare();
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    rezolva_problema();
    return 0;
}