#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

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

struct muchie
{
    int nod1,nod2,cost;
} rez[100010];

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

int tata[100010],h[100010],n,m,i,j,nrm,ans;
priority_queue <muchie, vector <muchie>, cmp> q;

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

void Union(int x, int y)
{
    if (h[x]<h[y])
        tata[x]=y;
    else if (h[x]>h[y])
        tata[y]=x;
    else
        tata[y]=x,h[x]++;
}

int main()
{
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        int a,b,c;
        fin >> a >> b >> c;
        muchie m;
        m.nod1=a;
        m.nod2=b;
        m.cost=c;
        q.push(m);
    }
    nrm=ans=0;
    while (nrm<n-1)
    {
        int cx,cy;
        muchie m=q.top();
        q.pop();
        cx=Find(m.nod1);
        cy=Find(m.nod2);
        if (cx!=cy)
        {
            Union(cx,cy);
            ans=ans+m.cost;
            rez[++nrm]=m;
        }
    }
    fout << ans << '\n' << nrm << '\n';
    for (i=1; i<=nrm; i++)
        fout << rez[i].nod1 << ' ' << rez[i].nod2 << '\n';
}