#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct muchie
{
    int x, y, w;
}muchii[400001];

bool verif(muchie a, muchie b)
{
    return a.w<b.w;
}

vector<vector<int>>sol;

int n, m, rk[200001], parent[200001];

int find(int i)
{
    if(parent[i]==0) return i;
    else parent[i]=find(parent[i]);
    return parent[i];
}

void uni(int f1, int f2)
{
    if(rk[f1]<rk[f2]) parent[f1]=f2;
    else if(rk[f2]<rk[f1]) parent[f2]=f1;
    else
    {
        parent[f2]=f1;
        rk[f1]++;
    }
}

int main()
{
    int s=0;
    fin >> n >> m;
    for(int i=1; i<=m; i++)
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].w;
    sort(muchii+1,muchii+m+1,verif);
    for(int i=1; i<=m; i++)
    {
        int f1=find(muchii[i].x), f2=find(muchii[i].y);
        if(f1!=f2)
        {
            s+=muchii[i].w;
            sol.push_back({muchii[i].x,muchii[i].y});
            uni(f1,f2);
        }
    }
    fout << s << '\n';
    fout << sol.size() << '\n';
    for(auto it:sol)
        fout << it[0] << ' ' << it[1] << '\n';
    return 0;
}