#include <fstream>
#include <algorithm>


using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");



int n,m;
int const MAX=200001;
int tata[MAX],inalt[MAX];
int cost;
int k;
int nr_muchii;

int get_king(int x)
{
    if(x==tata[x])
        return x;

    x=get_king(tata[x]);

    return tata[x];


}


pair<int,int>v[200000];

struct muchie{
int x;
int y;
int cost;
}a[MAX];

bool compare(muchie a,muchie b)
{
    if(a.cost < b.cost)
        return 1;
    return 0;


}




int main()
{
    fin>>n>>m;

    for(int i =1;i <= m; ++i)
    {
        int nod1,nod2,cost;

        fin>>nod1>>nod2>>cost;
        a[++k].x=nod1;
        a[k].y=nod2;
        a[k].cost=cost;
    }

    for(int i =1;i <= n; ++i)
    {
        tata[i]=i;
        inalt[i]=1;
    }

    sort(a+1,a+m+1,compare);



    int k =1;
    while(nr_muchii <= n-2)
    {
        int k1=get_king(a[k].x);
        int k2=get_king(a[k].y);


        if(k1 != k2){
        ++nr_muchii;
        v[nr_muchii].first=a[k].x;
        v[nr_muchii].second=a[k].y;
        cost+=a[k].cost;

        if(inalt[k1] > inalt[k2])
        {
            tata[k2]=k1;

        }
        else
        if(inalt[k1] < inalt[k2])
        {
            tata[k1]=k2;

        }
        else
        {
            tata[k2]=k1;
            inalt[k1]+=inalt[k2];
        }

        }
        ++k;
    }

    fout<<cost<<"\n";
    fout<<nr_muchii<<"\n";

    for(int i =1; i <= nr_muchii; ++i)
        fout<<v[i].first<<" "<<v[i].second<<"\n";


    return 0;
}