#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],rang[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 node1, int node2)
{
    node1 = Find(node1);
    node2 = Find(node2);
    if(node1 == node2)
        return;
    if(rang[node1] < rang[node2])
        swap(node1, node2);
    if(rang[node1] == rang[node2])
        rang[node1]++;
    TT[node2] = node1;
}

int main()
{
    fin>>n;
    fin>>m;
    for(int i=1;i<=n;i++)
    {
        TT[i]=i;
        rang[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(i.first.first,i.first.second);
        }
    }
    fout<<s<<'\n';
    fout<<sol.size()<<'\n';
    for(auto i : sol)
    {
        fout<<i.first<<' '<<i.second<<'\n';
    }
    return 0;
}