#include<fstream>
#include<iostream>
#include<vector>
#include<stdlib.h>
using namespace std;
int t=0,S=0;
int count1=0,count2=0;
vector <int> X[200005];
int V[400005]={0};
ifstream f("apm.in");
ofstream g("apm.out");

struct much
{
    int top,bot;

};

struct lalala
{
    int top,bot,cost;

};

much B[200005];

int new1(int a,int b,int c)
{
    count1++;
    B[count2].top=a;
    B[count2].bot=b;
    count2++;
    t++;
    V[a]=t;
    V[b]=t;
    S+=c;
    X[t].push_back(a);
    X[t].push_back(b);

    return 0;
}

int add1(int a,int b,int c)
{
    B[count2].top=a;
    B[count2].bot=b;
    count2++;
    count1++;
    V[a]=V[b];
    S+=c;
    X[V[b]].push_back(a);
    return 0;
}

int merge1(int a,int b,int c)
{
    B[count2].top=a;
    B[count2].bot=b;
    count2++;
    count1++;
    S+=c;
    for(vector<int>::iterator j=X[V[b]].begin();j!=X[V[b]].end();++j)
    {
        if(*j>200000)
        break;
        V[*j]=V[a];
    }
    return 0;
}



int compare(const void * a,const void * b)
{
    lalala x=*(lalala*)a;
    lalala y=*(lalala*)b;
    return(x.cost-y.cost);


}

lalala A[400005];

int main()
{
    int n,m,i,a,b,c;

    f>>n>>m;
    for(i=0;i<m;i++)
    {
        f>>a>>b>>c;
        A[i].top=a;
        A[i].bot=b;
        A[i].cost=c;
    }
    qsort(A,m,sizeof(lalala),compare);
    for(i=0;i<m&&count1<n-1;i++)
    {
        //cout<<V[A[i].top]<<' '<<V[A[i].bot]<<'\n';


        if(V[A[i].top]==0&&V[A[i].bot]==0)
            new1(A[i].top,A[i].bot,A[i].cost);
        else if(V[A[i].top]==0)
            add1(A[i].top,A[i].bot,A[i].cost);
        else if(V[A[i].bot]==0)
            add1(A[i].bot,A[i].top,A[i].cost);
        else if(V[A[i].top]>0&&V[A[i].bot]>0&&V[A[i].top]!=V[A[i].bot])
            merge1(A[i].top,A[i].bot,A[i].cost);
    }
   g<<S<<'\n'<<n-1<<'\n';
   for(i=0;i<count2;++i)
       g<<B[i].top<<' '<<B[i].bot<<'\n';
   return 0;




}