#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    bool operator<(muchie a) const
    {
        return this->cost<a.cost;
    }
    int x,y,cost;
};
int n,m,cost,*T;
muchie*M;
int radacina(int x)
{
    while(T[x]!=T[T[x]])
        T[x]=T[T[x]];
    return T[x];
}
bool union1(int x,int y)
{
    x=radacina(x),y=radacina(y);
    if(x!=y)
    {
        T[x]=T[y];
        return true;
    }
    return false;
}
int main()
{
    f>>n>>m;
    M=new muchie[m+1];
    T=new int[n+1];
    vector<bool>luat(n+1);
    for(int i=1; i<=n; ++i)
        T[i]=i;
    for(int i=0; i<m; ++i)
        f>>M[i].x>>M[i].y>>M[i].cost;
    stable_sort(M,M+m);
    for(int i=0; i<m; ++i)
        if(union1(M[i].x,M[i].y))
        {
            cost+=M[i].cost;
            luat[i]=true;
        }
    g<<cost<<'\n'<<n-1<<'\n';
    for(int i=0; i<m; ++i)
        if(luat[i])
            g<<M[i].y<<' '<<M[i].x<<'\n';
    delete []M;
    delete []T;
    return 0;
}