#include <algorithm>
#include <fstream>
#include <vector>
#include <utility>
#define pb push_back
#define f first
#define s second

using namespace std;
using pii=pair<int,int>;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int N=2e5+2;
const int M=4e5+2;

struct muchie{
    int x,y,cost;
    bool operator<(const muchie &o) const{
        return cost<o.cost;
    }
};

int n,m,x,y,z,sum,i;
int vf[N],rang[N];

vector<muchie> v;
vector<pii> ans;

int myfind(int x){
    if(vf[x]==x)
        return x;
    return vf[x]=myfind(vf[x]);
}

void sol(pii now){
    if(rang[now.f]>rang[now.s])
        vf[now.s]=now.f, rang[now.s]+=rang[now.f];
    else
        vf[now.f]=now.s, rang[now.f]+=rang[now.s];
}

int main()
{
    fin>>n>>m;
    for(i=0; i<m; i ++)
        fin>>x>>y>>z, v.pb({x,y,z});
    for(i=1; i<=n; i++)
        vf[i]=i, rang[i]=1;

    sort(v.begin(),v.end());

    sum=0;
    for(i=0; i<v.size(); i++)
    {
        if(myfind(v[i].x)!=myfind(v[i].y))
        {
            sol({myfind(v[i].x),myfind(v[i].y)});
            sum+=v[i].cost;
            ans.pb({v[i].x,v[i].y});
        }
    }

    fout<<sum<<'\n';
    fout<<ans.size()<<'\n';
    for(auto t:ans)
        fout<<t.f<<' '<<t.s<<'\n';
    fout<<'\n';
    return 0;
}