#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchii{
    int x,y,z;
};

int n,m,x,y,z,s,k,tata[200200],rang[200200];
vector <muchii> edges;
vector <pii> w;

bool compare(muchii a,muchii b){
    return a.z<b.z;
}

int rad(int x)
{
    if(x==tata[x])
        return x;
    tata[x]=rad(tata[x]);
    return tata[x];
}

int uneste(int a,int b)
{
    int ra=rad(a), rb=rad(b);
    if(ra!=rb)
    {
        if(rang[ra]>rang[rb])
            tata[rb]=ra;
        else
        {
            tata[ra]=rb;
            if(rang[ra]==rang[rb])
                rang[rb]++;
        }
    }
}

int32_t main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>x>>y>>z, edges.push_back({x,y,z});
    sort(edges.begin(),edges.end(),compare);
    for(int i=1; i<=n; i++)
        tata[i]=i;
    for(auto it:edges)
    {
        x=it.x, y=it.y;
        if(rad(x)!=rad(y))
            s+=it.z, uneste(x,y), w.push_back({x,y});
    }
    g<<s<<'\n'<<n-1<<'\n';
    for(auto it:w)
        g<<it.first<<' '<<it.second<<'\n';
    return 0;
}