#include <cstdio>
#include <vector>
#include <set>
#define mp make_pair
using namespace std;
int i, N, M, T[200001], Adanc[200001], Total, NR;
vector<pair<int, int> > Sol;
multiset<pair<int, pair<int, int> > > H;
int TataLor(int x)
{
    if (T[x]!=x) T[x]=TataLor(T[x]);
    return T[x];
}
void FamilyReunion(int x, int y)
{
    if (Adanc[x]<Adanc[y]) T[x]=y;
    else T[y]=x;
    if (Adanc[x]==Adanc[y]) Adanc[x]++;
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for (i=1; i<=M; i++)
    {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        H.insert(mp(cost, mp(x, y)));
    }
    for (i=1; i<=N; i++) T[i]=i,Adanc[i]=0;
    while (!H.empty())
    {
        multiset<pair<int, pair<int, int> > >::iterator X=H.begin();
        H.erase(X);
        int cost=(*X).first, x=(*X).second.first, y=(*X).second.second, Tx=TataLor(x), Ty=TataLor(y);
        if (Tx!=Ty)
        {
            FamilyReunion(Tx, Ty);
            Total+=cost;
            NR++;
            Sol.push_back(mp(x, y));
        }
    }
    printf("%d\n%d\n", Total, NR);
    for (vector<pair<int, int> >::iterator it=Sol.begin(); it!=Sol.end(); it++)
        printf("%d %d\n", (*it).first, (*it).second);
    return 0;
}