#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,T[200005],nr=0,cost=0;
struct mer{
    vector <int>x;
    vector <int>y;
    vector <int>c;
};
mer v;
struct compara {
bool operator()(int x,int y){
return v.c[x]>v.c[y];
}
};
priority_queue<int, vector<int > ,compara>q;
queue <int >z1;
queue <int> z2;

void citire()
{
    f>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++)
    {
         f>>x>>y>>c;
    v.x.push_back(x);
    v.y.push_back(y);
    v.c.push_back(c);
    q.push(i);
    }
}
void sortare()
{
    for(int i=1;i<=n;i++)
    {
        T[i]=i;
    }
}
void krusk()
{int x,y,i;
    while(!q.empty())
    {i=q.top();
    q.pop();

        if(T[v.x[i]]!=T[v.y[i]])
        {
            z1.push(v.x[i]);
            z2.push(v.y[i]);
            cost=cost+v.c[i];
            nr++;
            x=T[v.x[i]];
            y=T[v.y[i]];
            for(int j=1;j<=n;j++){
                if(x==T[j])T[j]=y;
            }
        }
    }
}
void afisare()
{
    g<<cost<<'\n';
    g<<nr<<'\n';
    int x,y;
    while(!z1.empty())
    {
        x=z1.front();
        y=z2.front();
        g<<x<<" "<<y<<'\n';
        z1.pop();
        z2.pop();

    }
}
int main ()
{ citire();
sortare();
krusk();
afisare();
}