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

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

struct str
{
    int nod,vecin,dist;
    bool operator <(const str &other)const
    {
        return dist>other.dist;
    }
};

struct str2
{
    int nod,vecin;
};

priority_queue<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({x1,x2,x3});
    }
}

void rez()
{
    while (!pq.empty())
    {
        int nod=pq.top().nod;
        int vecin=pq.top().vecin;
        int cost=pq.top().dist;
        pq.pop();
        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();
}