#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

struct muchie{int x,y,cost;};

struct subset
{
    int parent;
    int rank;
};

bool compar (muchie m1, muchie m2)
{
    return m1.cost < m2.cost;
}

int cauta (subset sets[], int v)
{
    if (sets[v].parent != v)
        sets[v].parent = cauta(sets, sets[v].parent);

    return sets[v].parent;
}

void uniune(subset subsets[], int x, int y)
{
    int xroot = cauta(subsets, x);
    int yroot = cauta(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;

    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

subset subseturi[200001];

int main()
{
    fstream f("apm.in",ios::in);
    fstream out("apm.out",ios::out);
    vector<muchie> u;
    vector<muchie> rez;
    int n,m,i,ma,costot=0,j,arbtemp,x,y,cost;


    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        muchie m;
        m.x=x;
        m.y=y;
        m.cost=cost;

        u.push_back(m);
    }
    sort(u.begin(), u.end(), compar);

    for(i=1;i<=n;i++)
    {
        //arb[i]=i;
        subseturi[i].parent = i;
        subseturi[i].rank = 0;
    }

    ma=0;
    i=0;

    while(ma < n-1)
    {
        x = cauta(subseturi, u[i].x);
        y = cauta(subseturi, u[i].y);

        if (x != y)
        {
            ma++;
            muchie mu;
            mu.x=u[i].x;
            mu.y=u[i].y;
            costot += u[i].cost;

            rez.push_back(mu);

            uniune(subseturi, x, y);
        }
    i++;
    }

    out<<costot<<endl<<n-1<<endl;

    for(i=0;i<n-1;i++)
        out<<rez[i].x<<" "<<rez[i].y<<endl;
}