#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nod vecini[add][i]

///KRUSKAL

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii{
    int x,y,ct;
}v[400005];
int n,m,tati[200005],arb[200005],root,add,k,cost;
vector<int> vecini[200005];

bool comp(muchii a, muchii b)
{
    return (a.ct<b.ct);
}

bool check(int i)
{
    return (tati[v[i].x]!=tati[v[i].y]);
}

void join(int j)
{
    root=tati[v[j].x];
    add=tati[v[j].y];
    if(arb[root]<arb[add]) swap(root,add);
    for(int i=0;i<vecini[add].size();++i)
    {
        vecini[root].push_back(nod);
        vecini[nod].resize(0);
        vecini[nod].push_back(root);
        tati[nod]=root;
    }
    vecini[root].push_back(add);
    vecini[add].resize(0);
    vecini[add].push_back(root);
    tati[add]=root;
    arb[root]+=arb[add];

    ///adaugare valori

    cost+=v[j].ct; ++k;
    v[k]=v[j];
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>v[i].x>>v[i].y>>v[i].ct;
    }
    sort(v+1,v+m+1,comp);
    for(int i=1;i<=n;++i) arb[i]=1, tati[i]=i;
    for(int i=1;i<=m;++i) if(check(i)) join(i);
    g<<cost<<'\n'<<k<<'\n';
    for(int i=1;i<=k;++i)
    {
        g<<v[i].x<<' '<<v[i].y<<'\n';
    }
    return 0;
}