#include <bits/stdc++.h>
#define Nmax 200005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y,cost;
};
muchie v[Nmax*2];
struct comp
{
    bool operator()(muchie a, muchie b)
    {
        return a.cost < b.cost;
    }

};
int n,m;
int root[Nmax];
int dim[Nmax];
void citire()
{
    f>>n>>m;
    for( int i = 1;i <=m; i++)
        f>>v[i].x>> v[i].y>>v[i].cost;
    sort(v+1,v+m+1,comp());

}
int find_rad(int p)
{
    int radacina= p ;
    while(root[radacina] != radacina)
        radacina=root[radacina];
    while ( p !=radacina)
    {
        int urm = root[p];
        root[p] = radacina;
        p= urm ;

    }
    return radacina;
}
int uniune(int p ,  int q)
{
    int rad1=find_rad(p);
    int rad2=find_rad(q);
    if(rad1 !=  rad2)
    {
        if(dim[rad1] < dim[rad2])
        {
         dim[rad1] += dim[rad2];
         root[p]=q;
        }
        else
        {
              dim[rad2] += dim[rad1];
               root[q]=p;

        }
        return 1;
    }
    return 0;
}
struct linie
{
    int st,dr;
};
linie muchii [Nmax];
int k;
void kruskal()
{
    int i,cost_f=0;
    for(i=1;i<=n;i++)
        {
            root[i]=i;
            dim[i]=1;
        }
    for( i = 1 ; i <= m ;i++)
    {
        int rad1=find_rad(v[i].x);
        int rad2=find_rad(v[i].y);
        if(uniune(rad1,rad2))
        {
            cost_f = cost_f + v[i].cost;
            k++;
            muchii[k].st=v[i].x;
            muchii[k].dr=v[i].y;
        }
    }
    g<<cost_f<<endl;
    g<<n-1<<endl;
    for(i=1;i<=k;i++)
        g<<muchii[i].st<<" "<<muchii[i].dr<<endl;
}

int main()
{
    citire();
    kruskal();
    return 0;
}