#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y,c,viz;
}v[400003];
int t[200002],sz[200002],n,m,nr;
long long s;
bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}
void kruskal()
{
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
        sz[i]=1;
    }
    sort (v+1,v+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int a=v[i].x,b=v[i].y;
        while(a!=t[a])
            a=t[a];
        while(b!=t[b])
            b=t[b];
        if(t[a]!=t[b])
        {
            s+=v[i].c;
            v[i].viz=1;
            nr++;
            if(sz[a]>sz[b])
            {
                sz[a]+=sz[b];
                t[b]=a;
            }
            else
            {
                sz[b]+=sz[a];
                t[a]=b;
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    kruskal();
    g<<s<<'\n'<<nr<<'\n';
    for(int i=1;i<=m;i++)
        if(v[i].viz==1)
        g<<v[i].x<<" "<<v[i].y<<'\n';
    return 0;
}