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

using namespace std;

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

vector<pair<int, pair <int, int > > > v;
vector<pair<int, int > > sol;
int n, m, a, b, c,t, s=0, p[400001];

int find_(int x)
{
    if(p[x]<0)
        return x;
    else
        return x=find_(p[x]);
}

void union_(int a, int b)
{
    int parenta=find_(a);
    int parentb=find_(b);
    if(p[parenta]>p[parentb])
        p[parenta]=parentb;
    else if(p[parenta]<p[parentb])
        p[parentb]=parenta;
    else if(p[parenta]==p[parentb])
       {
        p[parenta]=parentb;
        p[parentb]--;
       }
}



int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v.push_back(make_pair(c,make_pair(a,b)));
    }
    sort(v.begin(),v.end());

    for(int i=1;i<=n;i++)
        p[i]=-1;

    for(int i=0;i<m;i++)
    {
        int x=find_(v[i].second.first);
        int y=find_(v[i].second.second);
        if(x!=y)
        {
            s+=v[i].first;
            sol.push_back(make_pair(v[i].second.first,v[i].second.second));
            union_(x,y);
            //cout<<v[i].second.first<<" "<<v[i].second.second<<'\n';
            t++;

        }
        if(t==n-1)
            break;
    }
    fout<<s<<'\n';
    fout<<t<<'\n';
    for(int i=0;i<sol.size();i++)
        fout<<sol[i].first<<" "<<sol[i].second<<'\n';
    return 0;
}