#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

priority_queue< pair<int, pair<int,int> > > muchii;
vector< pair<int,int> >graf_final;
int tata[2000003];
int grad[2000000];
int find_father(int node)
{
    if(tata[node]==node)
        return node;
    tata[node]=find_father(tata[node]);
    return tata[node];
}
int main()
{
    int n,m,x,y,c,i;
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;

    for(i=1;i<=n;i++)
    {
        grad[i]=1;
        tata[i]=i;
    }
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        muchii.push(make_pair((-1*c),make_pair(x,y)));
    }

    int cost=0;

    while(!muchii.empty())
    {
        pair<int,int>muchie;
        pair<int,pair<int,int> >p=muchii.top();
        muchii.pop();
        muchie=p.second;
        int t_first,t_second;
        t_first=find_father(muchie.first);
        t_second=find_father(muchie.second);
        if(t_first!=t_second)
        {
            if(grad[t_first]<grad[t_second])
            {
                tata[t_first]=t_second;
                grad[t_second]+=grad[t_first];
                graf_final.push_back(make_pair(muchie.first,muchie.second));
                cost+=(-1)*p.first;
            }
            else
            {
                tata[t_second]=t_first;
                grad[t_first]+=grad[t_second];
                graf_final.push_back(make_pair(muchie.first,muchie.second));
                cost+=(-1)*p.first;
            }
        }

    }
    fout<<cost<<endl;
    fout<<graf_final.size()<<endl;
    for(i=0;i<graf_final.size();i++)
    fout<<graf_final[i].first<<" "<<graf_final[i].second<<endl;
    return 0;
}