#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,nr=0,cost=0;
struct mer{
    vector <int>x;
    vector <int>y;
    vector <int>c;
};mer v;
struct ter{
int arbore;
int marime;
};
ter T[200005];

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].arbore=i;
        T[i].marime=1;
    }
}
void compara(int x,int y,int x1,int y1)
{
    for(int i=1;i<=n;i++)
    {
        if(T[i].arbore==x){
            T[i].arbore=y;
            T[i].marime=x1+y1;
        }
        else
            if(T[i].arbore==y)T[i].marime=x1+y1;
    }

}
void krusk()
{int x,y,i;
    while(!q.empty())
    {i=q.top();
    q.pop();
        if(T[v.x[i]].arbore!=T[v.y[i]].arbore)
        { x=v.x[i];
            y=v.y[i];
            z1.push(v.x[i]);
            z2.push(v.y[i]);
            cost=cost+v.c[i];
            nr++;

            if(T[x].marime>T[y].marime)swap(x,y);
            compara(T[x].arbore,T[y].arbore,T[x].marime,T[y].marime);
            }
        }
    }
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();
}