//kruskal O(NlogN)
#include <bits/stdc++.h>

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

struct muchie{
    int from,to,cost;
};
int n,m;
muchie muchii[400001];
vector<pair<int,int>> sol;
vector<int> tata, dim;
int apm = 0;

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>muchii[i].from >> muchii[i].to >> muchii[i].cost;
}

bool cmp(const muchie a, const muchie b)
{
    return a.cost<b.cost;
}

int root(int x)
{
    while(x!= tata[x])
    {
        tata[x] = tata[tata[x]];
        x = tata[x];
    }
    return x;
}

void unire(int rootx,int rooty)
{
    if(dim[rootx]>dim[rooty])
    {
        dim[rootx] += dim[rooty];
        tata[rooty] = rootx;
    }
    else
    {
        dim[rooty] += dim[rootx];
        tata[rootx] = rooty;
    }
}


void solve_kruskal()
{
    dim.resize(n+1,1);
    tata.resize(n+1);
    iota(tata.begin(),tata.end(),0);

    sort(muchii+1, muchii+m+1, cmp);
    for(int i=1;i<=m;i++)
    {
        int rootx = root(muchii[i].from);
        int rooty = root(muchii[i].to);
        if(rootx!=rooty)
        {
            apm+= muchii[i].cost;
            sol.emplace_back(muchii[i].from, muchii[i].to);
            unire(rootx,rooty);
        }
    }
}

int main()
{
    citire();
    solve_kruskal();
    fout<<apm<<'\n';
    fout<<sol.size()<<'\n';
    for(auto pereche: sol)
        fout<<pereche.first<<' '<<pereche.second<<'\n';
    return 0;
}