#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

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

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

    vector<int> apm[200001];

int main()
{
    fstream f("apm.in",ios::in);
    fstream out("apm.out",ios::out);
    muchie g;
    vector<muchie> u;
    int n,m,arb[200001],i,ma,costot=0,j;
    f>>n>>m;

    for(i=1; i<=m; i++)
    {
        f>>g.x>>g.y>>g.cost;
        u.push_back(g);
    }

    sort(u.begin(),u.end(),comp);

    for(i=1; i<=n; i++)
        arb[i]=i;

    ma=0;//nr de muchii din arbore
    i=0;//muchia curenta

    while(ma < n-1)
    {
        if(arb[u[i].x] != arb[u[i].y])
        {
            costot += u[i].cost;
            apm[u[i].x].push_back(u[i].y);
            ma++;

            for(j=1; j<=n; j++)
                if(arb[j]==arb[u[i].y])
                    arb[j]=arb[u[i].x];
        }
        i++;//trec la muchia urmatoare
    }
    out<<costot<<endl<<n-1<<endl;

   for(i=1;i<=n;i++)
        for(j=0;j<apm[i].size();i++)
            out<<i<<" "<<apm[i][j]<<endl;

    return 0;
}