#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 200005

using namespace std;

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

vector<pair<pair<int,int>,int>> v;
vector<pair<int,int>> sol;
int TT[Nmax];
int n,m,a,b,x,y,c,s;

int Find(int nod)
{
    if(TT[nod]==nod)
        return nod;
    else
        return Find(TT[nod]);
}

void Unite(int x , int y)
{
    TT[y]=x;
}

int main()
{
    fin>>n;
    fin>>m;
    for(int i=1;i<=n;i++)
    {
        TT[i]=i;
    }
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        v.push_back(make_pair(make_pair(x,y),c));
    }
    sort(v.begin(),v.end(), [](auto &left , auto &right)
         {
             return left.second<right.second;
         });
    for(auto i : v)
    {
        int a = Find(i.first.first);
        int b = Find(i.first.second);
        if(a!=b)
        {
            s+=i.second;
            sol.push_back(make_pair(i.first.first,i.first.second));
            Unite(a,b);
        }
    }
    fout<<s<<'\n';
    fout<<sol.size()<<'\n';
    for(auto i : sol)
    {
        fout<<i.first<<' '<<i.second<<'\n';
    }
    return 0;
}