#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

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

struct str
{
    int nod,vecin,dist;
};

bool cmp(str x, str y)
{
    return x.dist<y.dist;
}

struct str2
{
    int nod,vecin;
};

vector<str>pq;
vector<str2>Q;

int n,m,nr,costt;
int p[200002];

int parinte(int x)
{
    if (p[x]==x)
        return x;
    return p[x]=parinte(p[x]);
}

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

void cit()
{
    f>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int x1,x2,x3;
        f>>x1>>x2>>x3;
        pq.push_back({x1,x2,x3});
    }
    sort(pq.begin(),pq.end(),cmp);
}

void rez()
{
    for (auto j:pq)
    {
        int nod=j.nod;
        int vecin=j.vecin;
        int cost=j.dist;
        if (!p[nod])
        {
            if (!p[vecin])
            {
                p[nod]=p[vecin]=nod;
                Q.push_back({nod,vecin});
                costt+=cost;
            }
            else
            {
                p[nod]=vecin;
                Q.push_back({vecin,nod});
                costt+=cost;
            }
        }
        else
        {
            if (!p[vecin])
            {
                p[vecin]=nod;
                Q.push_back({nod,vecin});
                costt+=cost;
            }
            else
            {
                if (parinte(vecin)==parinte(nod))
                    continue;
                unire(nod,vecin);
                Q.push_back({nod,vecin});
                costt+=cost;
            }
        }
    }
}

void afis()
{
    g<<costt<<'\n'<<n-1<<'\n';
    for (auto w:Q)
    {
        g<<w.nod<<' '<<w.vecin<<'\n';
    }
}

int main()
{
    cit();
    rez();
    afis();
}