#include <bits/stdc++.h>
using namespace std;

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

#define piii pair<pair<int,int>,int>
#define pii pair<int,int>
const int N=2e5+5;

vector<piii> v;
int tata[N],rang[N];

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

bool comp(piii a, piii b)
{
    return a.second < b.second;
}

void reuniune(int x, int y)
{
    int rad1 = radacina(x), rad2 = radacina(y);

    if(rang[rad1] > rang[rad2]) tata[rad2]=rad1;
    else
    {
        tata[rad1]=rad2;
        if(rang[rad1] == rang[rad2]) rang[rad2]++;
    }
}

int main()
{
    int n,m; in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y,c; in>>x>>y>>c;

        v.push_back({{x,y},c});
    }

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

    for(int i=1;i<=n;i++)
        tata[i]=i;

    int costMIN=0;
    vector<pii> apm;
    for(int i=0;i<v.size();i++)
    {
        pii muchie = v[i].first;
        if(radacina(muchie.first) != radacina(muchie.second))
        {
            costMIN+=v[i].second;
            reuniune(muchie.first,muchie.second);
            apm.push_back(muchie);
        }
    }

    out<<costMIN<<'\n'<<apm.size()<<'\n';

    for(int i=0;i<apm.size();i++)
        out<<apm[i].first<<' '<<apm[i].second<<'\n';
}