#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
struct vec{
    int x;
    int y;
    int c;
    bool apm;
}v[400003];
int p[200003];
int rang[200003];
bool comp(struct vec a,struct vec b)
{
    return a.c<b.c;
}
inline void createSet(int i)
{
    p[i]=i;
    rang[i]=0;
}
int findSet(int i)
{
    if(p[i]!=i)
        p[i]=findSet(p[i]);//path compression
    return p[i];
}
bool mergeSet(int a,int b)
{
    int aroot=findSet(a);
    int broot=findSet(b);
    if(aroot==broot)
        return 0;
    else
    {
        if(rang[aroot]>rang[broot])
            p[broot]=aroot;
        else if(rang[aroot]<rang[broot])
            p[aroot]=broot;
        else
        {
            p[broot]=aroot;
            rang[aroot]++;
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,comp);
    for(int i=1;i<=n;i++)
        createSet(i);
    int nr=0;
    int i=1;
    int cost=0;
    while(nr<n&&i<=m)
    {
        if(mergeSet(v[i].x,v[i].y))
        {
            cost+=v[i].c;
            nr++;
            v[i].apm=true;
        }
        i++;
    }
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=1;i<=m;i++)
        if(v[i].apm)
            g<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}