#include <bits/stdc++.h>

using namespace std;

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

vector < pair < int , int > > sol;
int tata[200100],h[200100];
struct muchie
{
    int x,y,c;
}v[400100];

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

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

int uneste(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;
}

int n,m,i,s,muchii_puse;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,compare);

    for(i=1;i<=n;i++)h[i]=1,tata[i]=0;
    muchii_puse=0;i=1;
    while(muchii_puse<n-1)
    {
        if(uneste(v[i].x,v[i].y))
        {
            muchii_puse++;
            s+=v[i].c;
            sol.push_back({v[i].x,v[i].y});
        }
        i++;
    }

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