#include <bits/stdc++.h>

using namespace std;

struct Muchie{
    int x, y, c;
    bool folosita;
};

Muchie L[400003];
int t[200003], sol;
int n,m;
int indm=0;

void Citire()
{
    int i;
    ifstream fin("kruskal.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        Muchie w;
        fin>>w.x>>w.y>>w.c;
        indm++;
        L[indm] = w;
    }
    fin.close();
}

bool CMP(const Muchie A, const Muchie B)
{
    return A.c<B.c;
}

void Union (int r1,int r2)
{
    //cout<<"r1 = "<<r1<<"\n";
    //cout<<"r2 = "<<r2<<"\n";
   t[r2]=r1;
}
int Find(int x)
{
    while(t[x]!=0)
    {
        //cout<<"\t\tx="<<x<<", t[x]="<<t[x]<<"\n";
        x = t[x];
    }
    return x;
}

void Kruskal()
{
    int i;
    Muchie w;

    sort(L+1, L+m+1, CMP);//sorteaza cele M muchii in functie de cost

    for(i=1;i<=m;++i)
    {
        //cout<<"i="<<i<<"\n";
        w = L[i];
        int r1, r2;
        r1 = Find(w.x);
        r2 = Find(w.y);
        //cout<<"\t";
        //cout<<"r1="<<r1<<", r2="<<r2<<"\n";
        if(r1!=r2)
        {
            L[i].folosita = true;
            Union(r1, r2);
            sol = sol + L[i].c;
        }
    }
}

int main()
{
    Citire();
    Kruskal();
    ofstream fout("kruskal.out");
    fout<<sol<<"\n";
    fout<<n<<"\n";
    for(int i=1;i<=m;++i)
        if(L[i].folosita==true)
            fout<<L[i].x<<" "<<L[i].y<<"\n";
    fout.close();
    return 0;
}