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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y;
};
struct nod
{
    int c;
    muchie m;
};
struct compar
{
    bool operator() (nod x, nod y)
    {
        return x.c>y.c;
    }
};
priority_queue <nod, vector <nod>, compar > Q;
vector <muchie> Sol;
int n,m,cost=0;
int dad[200001];
void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        nod a;
        fin>>a.m.x>>a.m.y>>a.c;
        Q.push(a);
    }
}
void afish()
{
    fout<<cost<<"\n"<<n-1<<"\n";
    for(auto &v: Sol)
        fout<<v.x<<" "<<v.y<<"\n";
}
void init()
{
    for(int i=1; i<=n; i++)
        dad[i]=i;
}
int daddy(int x)
{
    if(dad[x]==x) return x;
    else return daddy(dad[x]);
}
void kruskal()
{
    int a,b,i=1,dx,dy;
    while(i<=n-1)
    {
        a=Q.top().m.x;
        b=Q.top().m.y;
        dx=daddy(a);
        dy=daddy(b);
        if(dx!=dy)
        {
            i++;
            dad[max(dx,dy)]=min(dx,dy);
            cost+=Q.top().c;
            Sol.push_back(Q.top().m);
        }
        Q.pop();
    }
}
int main()
{
    citire();
    init();
    kruskal();
    afish();
    return 0;
}