#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
int p[200003];
int rang[200003];
struct muchii
{
    int x;
    int y;
    int c;
}v[400003],sol[200003];
bool comp(struct muchii a,struct muchii b)
{
    return a.c<b.c;
}
inline void create_set(int i)
{
    p[i]=i;
    rang[i]=0;
}
int find_set(int i)
{
    if(p[i]!=i)
        p[i]=find_set(p[i]);
    return p[i];
}
int merge_set(int a,int b)
{
    int aroot=find_set(a);
    int broot=find_set(b);
    if(aroot==broot)
    {
        return 0;
    }
    else
    {
        if(rang[aroot]>rang[broot])
            p[broot]=aroot;
        else if(rang[broot]>rang[aroot])
            p[aroot]=broot;
        else
        {
            rang[aroot]++;
            p[broot]=aroot;
        }
        return 1;
    }
}
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);
    //punem nodurile in multime diferita
    for(int i=1;i<=n;i++)
        create_set(i);
    //kruskal
    int nr=0;
    int i=1;
    int cost=0;
    while(nr<n&&i<=m)
    {
        if(merge_set(v[i].x,v[i].y))
        {
            cost+=v[i].c;
            nr++;
            sol[nr].x=v[i].x;
            sol[nr].y=v[i].y;
        }
        i++;
    }
    g<<cost<<"\n"<<nr<<"\n";
    for(int i=1;i<=nr;i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<"\n";
    }
    return 0;
}