#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,t[200003],s,sz[200003];
struct muchie
{
    int x,y,c,viz;
} v[400003];
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;
        if(t[a]!=t[b])
        {
            while(t[a]!=a)
                a=t[a];
            while(t[b]!=b)
                b=t[b];
            if(a!=b)
            {
                s+=v[i].c;
                v[i].viz=1;
                if(sz[a]<sz[b])
                {
                    t[a]=b;
                    sz[b]+=sz[a];
                }
                else
                {
                    t[b]=a;
                    sz[a]+=sz[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';
    g<<n-1<<'\n';
    for(int i=1; i<=m; i++)
        if(v[i].viz)
            g<<v[i].x<<" "<<v[i].y<<'\n';
    return 0;
}