#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector<pair<int,int> >v;
int p[200001],n,m;

struct muchiee
{
    int x,y,z;
}muchie[200005];
bool cmp(muchiee A,muchiee B)
{
    return A.z<B.z;
}
int parinte(int x)
{
    if(p[x]==x)return x;
    else return p[x]=parinte(p[x]);
}
void unite(int x,int y)
{
    p[parinte(y)]=parinte(x);
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>muchie[i].x>>muchie[i].y>>muchie[i].z;

    }
    int c=0;
    for ( int i = 1; i <= n; i ++ ) p[i] = i;
    sort(muchie+1,muchie+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(parinte(muchie[i].x)!=parinte(muchie[i].y))
        {
            unite(parinte(muchie[i].x),parinte(muchie[i].y));
            c=muchie[i].z+c;
            v.push_back({muchie[i].x,muchie[i].y});
        }
    }
    fout<<c<<'\n'<<v.size()<<'\n';
    for(int i=0;i<v.size();i++)
        fout<<v[i].first<<" "<<v[i].second<<'\n';
    return 0;
}