#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX=400005;

pair<int, int>P[NMAX];
int cnt;

int n, m, total, t[NMAX], rg[NMAX], tx, ty;

struct Muchie
{
    int u, v, cost;
}muchii[NMAX];

bool cmp(Muchie a, Muchie b)
{
    return a.cost<b.cost;
}

int FindSet(int nod)
{
    while(t[nod]!=nod)
        nod=t[nod];
    return nod;
}

void UnionSet(int x, int y)
{
    if(rg[x]>rg[y])
        t[y]=x;
    else
        if(rg[y]>rg[x])
            t[x]=y;
        else
        {
            t[x]=y;
            rg[y]++;
        }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>muchii[i].u>>muchii[i].v>>muchii[i].cost;
    sort(muchii+1, muchii+m+1, cmp);
    for(int i=1; i<=n; i++)
    {
        t[i]=i;
        rg[i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        tx=FindSet(muchii[i].u);
        ty=FindSet(muchii[i].v);
        if(tx!=ty)
        {
            UnionSet(tx, ty);
            P[++cnt].first=muchii[i].u;
            P[cnt].second=muchii[i].v;
            total=total+muchii[i].cost;
        }
    }
    fout<<total<<"\n";
    fout<<cnt<<"\n";
    for(int i=1; i<=cnt; i++)
        fout<<P[i].first<<" "<<P[i].second<<"\n";
    return 0;
}