#include <fstream>


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];




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;
    }

    for(int i =1;i < m; ++i)
        for(int j=i+1; j <= m; ++j)
        if(a[i].cost > a[j].cost)
        swap(a[i],a[j]);

    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]+=1;
        }

        }
        ++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;
}