#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define Nmax 200010
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y,cost;
};
vector <muchie> v;

int n,m,parent[Nmax],sum;
int arbx[Nmax],arby[Nmax],vf;

int cmp(muchie a,muchie b)
{
    return a.cost < b.cost;
}
int getRoot(int x)
{
    if(parent[x]!=x)
        parent[x]=getRoot(parent[x]);
    return parent[x];
}
void Union(int x,int y)
{
    x=getRoot(x);
    y=getRoot(y);
    parent[x]=y;
}
int main()
{
    f >> n >> m;
    int a,b,c;
    for(int i=0;i<m;i++)
    {
        f >> a >> b >>c ;
        v.push_back({a,b,c});
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=1;i<=n;i++)
        parent[i]=i;

    for(int i=0;i<v.size();i++)
    {
        if(getRoot(v[i].x)!=getRoot(v[i].y))
        {
            Union(v[i].x,v[i].y);
            sum+=v[i].cost;
            arbx[vf]=v[i].y;
            arby[vf]=v[i].x;
            vf++;
        }
    }

    g << sum << "\n";
    g << vf << "\n";
    for(int i=0;i<vf;i++)
        g << arbx[i] << " " << arby[i] << "\n";
    return 0;
}