#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#define pu(x) ((x^(x-1))&x)

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int nod1,nod2,cost;
} apm[200010];

class cmp
{
public:
    bool operator()(muchie A, muchie B)
    {
        return A.cost>B.cost;
    }
};

priority_queue <muchie, vector <muchie>, cmp> q;
int n,M,i,p[200010];

void Union(int x, int y)
{
    p[x]=y;
}

int Find(int x)
{
    int rad=x;
    while (p[rad]!=rad)
        rad=p[rad];
    while (p[x]!=rad)
    {
        int aux=p[x];
        p[x]=rad;
        x=aux;
    }
    return rad;
}

int main()
{
    fin >> n >> M;
    for (i=1; i<=M; i++)
    {
        muchie m;
        fin >> m.nod1 >> m.nod2 >> m.cost;
        q.push(m);
    }
    for (i=1; i<=n; i++)
        p[i]=i;
    int nr=0,ans=0;
    while (!q.empty())
    {
        muchie m=q.top();
        q.pop();
        int x,y;
        x=Find(m.nod1);
        y=Find(m.nod2);
        if (x==y)
            continue;
        Union(x,y);
        apm[++nr].nod1=x;
        apm[nr].nod2=y;
        ans+=m.cost;
    }
    fout << ans << '\n';
    fout << n-1 << '\n';
    for (i=1; i<n; i++)
        fout << apm[i].nod1 << ' ' << apm[i].nod2 << '\n';
}