#include<fstream>
#include<algorithm>
#define Max 400005

using namespace std;

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

pair <int,int> P[Max];

int N,M,cost,TT[Max],k,RG[Max];

struct muchie
{
    int x,y,c;

};

muchie V[Max];

bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}

void read()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
        f>>V[i].x>>V[i].y>>V[i].c;
    sort(V+1,V+M+1,cmp);
}

int find(int nod)
{
    while(TT[nod]!=nod)
        nod=TT[nod];
    return nod;
}

void lipeste(int x,int y)
{
    if(RG[x]<RG[y])
        TT[x]=y;
    if(RG[y]<RG[x])
        TT[y]=x;
    if(RG[x]==RG[y])
    {
        TT[x]=y;
        RG[y]++;
    }
}


void apm()
{
    for(int i=1;i<=M;i++)
        if(find(V[i].x)!=find(V[i].y))
        {
            lipeste(find(V[i].x),find(V[i].y));
            P[++k].first=V[i].x;
            P[k].second=V[i].y;
            cost+=V[i].c;
        }
}

int main()
{
    read();
    for(int i=1;i<=M;i++)
        TT[i]=i,RG[i]=1;
    apm();
    g<<cost<<"\n";
    g<<N-1<<"\n";
    for(int i=1;i<=k;i++)
        g<<P[i].first<<" "<<P[i].second<<"\n";
    return 0;
}