#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct Muchie
{
    int x,y,cost;
};

bool cmp_muchii(Muchie m1,Muchie m2)
{
    return m1.cost<m2.cost;
}

int reprezentant(int x,vector<int>&parinte)
{
    if (x==parinte[x])
        return x;
    return parinte[x]=reprezentant(parinte[x],parinte); //compresia drumurilor
}

bool verify(int a,int b,vector<int>&parinte)
{
    return reprezentant(a,parinte)==reprezentant(b,parinte);
}

void unit(int a,int b,vector<vector<int>>&apm,vector<int>&parinte,vector<int>&adancime)
{
    apm[a].push_back(b);
    apm[b].push_back(a);

    int rep_a=reprezentant(a,parinte);
    int rep_b=reprezentant(b,parinte);

    if (adancime[rep_a]<adancime[rep_b])
        parinte[rep_a]=rep_b;
    else
        parinte[rep_b]=rep_a;

    if (adancime[rep_a]==adancime[rep_b])
        adancime[rep_a]++;
}

int main()
{
    int n,m;

    f>>n>>m;

    vector<vector<int>>apm(n+1);
    vector<Muchie>muchii(m);
    vector<int>parinte(n+1);
    vector<int>adancime(n+1,0);

    for (int i=1;i<=n;i++)
        parinte[i]=i; //initial fiecare nod se afla in propria lui componenta conexa

    for (int i=0;i<m;i++)
        f>>muchii[i].x>>muchii[i].y>>muchii[i].cost;

    sort(muchii.begin(),muchii.end(),cmp_muchii);

    int cost=0;
    for (auto muchie:muchii)
        if (!verify(muchie.x,muchie.y,parinte))
    {
        unit(muchie.x,muchie.y,apm,parinte,adancime);
        cost+=muchie.cost;
    }

    g<<cost<<'\n';
    g<<n-1<<'\n';

    for (int i=1;i<=n;i++)
    {
        for (auto vecin:apm[i])
            if (vecin>i)
                g<<i<<" "<<vecin<<'\n';
    }
}