#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <queue>

using namespace std;

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

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

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

priority_queue <muchie, vector <muchie>, cmp> q;

int p[100010],n,m,i,j,nr,ans;

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

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

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