#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,c,total;
int v[200001];
vector<pair <int,pair<int,int> > > muchii;
queue<pair<int,int> > q;

int rad(int nod)
{
    while(nod!=v[nod])
    {
        nod=v[nod];
    }
    return nod;
}
void uneste(int nod1,int nod2)
{
    int nod=rad(nod2);
    v[rad(nod1)]=v[rad(nod2)];
    while(nod1!=nod)
    {
        int aux=v[nod1];
        v[nod1]=nod;
        nod1=aux;
    }
       while(nod2!=nod)
    {
        int aux=v[nod2];
        v[nod2]=nod;
        nod2=aux;
    }
    
}


int main()
{
    fin>>n>>m;
    muchii.resize(m+1);
    for(int i=1; i<=m; ++i)
    {
        fin>>muchii[i].second.first;
        fin>>muchii[i].second.second;
        fin>>muchii[i].first;

    }
    sort(muchii.begin()+1, muchii.end());
    /*for(int i=1; i<=m; ++i)
    {
        fout<<muchii[i].second.first<<" ";
        fout<<muchii[i].second.second<<" ";
        fout<<muchii[i].first<<" ";
        fout<<"\n"; 
    }*/
    for(int i=1;i<=n;i++)
    {
        v[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x=muchii[i].second.first;
        int y=muchii[i].second.second;
        if(rad(x)!=rad(y))
        {
            uneste(x,y);
            c+=muchii[i].first;
            total++;
            q.push(make_pair(x,y));
        }
    }
    fout<<c<<"\n"<<total<<"\n";
    while(!q.empty())
    {
        fout<< q.front().first<<" "<< q.front().second<<"\n";
        q.pop();
    }
    return 0;
}