#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int x,y,cost;
}mch[200100];

int cost,n,tata[200100],h[200100];
vector < pair < int , int > > sol;

int compare(muchie A, muchie B)
{
    return(A.cost<B.cost);
}

int afla_radacina(int nod)
{
    while(tata[nod]!=0)nod=tata[nod];
    return nod;
}

int apm_muchie(int nod1, int nod2)
{
    int r1=afla_radacina(nod1);
    int r2=afla_radacina(nod2);

    if(r1==r2)return 0;

    if(h[r1]<h[r2])tata[r1]=r2;
    else if(h[r2]<h[r1])tata[r2]=r1;
    else tata[r1]=r2,h[r2]++;

    return 1;
}

void kruskal()
{
    int muchii_puse=0,i=1;
    while(muchii_puse<(n-1))
    {
        if(apm_muchie(mch[i].x,mch[i].y))
        {
            sol.push_back({mch[i].x,mch[i].y});
            cost+=mch[i].cost;
            muchii_puse++;
        }
        i++;
    }
}

int m,i;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>mch[i].x>>mch[i].y>>mch[i].cost;
    }
    sort(mch+1,mch+m+1,compare);
    kruskal();

    g<<cost<<'\n';
    g<<sol.size()<<'\n';
    for(i=0;i<sol.size();i++)g<<sol[i].first<<" "<<sol[i].second<<'\n';
    return 0;
}