#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#define dim 200003
int n,m;
struct muchie
{
    int x,y,c;
};
vector<muchie> v;
vector<int> t;
vector<pair<int,int>> q;
bool comp(muchie a ,muchie b)
{
    return a.c<b.c;
}
bool fr[dim];
int tata(int x)
{
    if(x==t[x])
        return x;
    int aux=tata(t[x]);
    t[x]=aux;
    return aux;
}

//Kruskal
int main()
{
    int nr=0,i,tx,ty,j,s=0;
    muchie a;
    fin>>n>>m;
    t.resize(n+1);
    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=0;i<m;i++)
    {
        fin>>a.x>>a.y>>a.c;
        v.push_back(a);
    }
    sort(v.begin(),v.end(),comp);
    for(i=0;i<v.size() && nr<n;i++)
    {
        tx=tata(v[i].x);
        ty=tata(v[i].y);
        if(tx!=ty)
        {
            t[tx]=ty;
            q.push_back(make_pair(v[i].x,v[i].y));
            nr++;
            s+=v[i].c;
        }
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for(i=0;i<q.size();i++)
    {
        fout<<q[i].first<<" "<<q[i].second<<'\n';
    }
    return 0;
}