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

using namespace std;
#define Nmax 100007
ifstream f("apm.in");
ofstream g("apm.out");

int parinte[Nmax],greutate[Nmax];
int find(int x)
{
    if(parinte[x]==x) return x;
    return parinte[x] = find(parinte[x]);
}

void unite(int x, int y)
{
    int parinte_x = find(x);
    int parinte_y = find(y);
    if(parinte_x!=parinte_y)
    {
        if(greutate[parinte_x]<greutate[parinte_y])
            swap(parinte_x,parinte_y);
        parinte[parinte_y]=parinte_x;
        greutate[parinte_x]+=greutate[parinte_y];
    }

}

void kruskall(vector< pair < int, pair <int,int>> > muchii)
{
    vector <pair <int,int> > arbore;
    int cost = 0;
    int numar_muchii = 0;
    sort(muchii.begin(),muchii.end());
    for(auto muchie:muchii)
    {
        if(find(muchie.second.second)!=find(muchie.second.first))
        {
            unite(muchie.second.second,muchie.second.first);
            cost+=muchie.first;
            numar_muchii ++;
            arbore.push_back(make_pair(muchie.second.second,muchie.second.first));
        }

    }
     g<<cost<<endl<<numar_muchii<<endl;
     for(int i=0;i<numar_muchii;i++)
        g<<arbore[i].first<<" "<<arbore[i].second<<endl;
}

int main()
{
    int n,m;
    vector< pair < int, pair <int,int> > > muchii;
    f>>n>>m;
    for(int i=1;i<=n;i++){
        parinte[i]=i;
        greutate[i]=1;
    }

    for(int i=0;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        muchii.push_back(make_pair(z,make_pair(x,y)));
    }
    kruskall(muchii);
    /*
    int n,m,op,x,y;
    f>>n>>m;

    for(int i=0;i<m;i++)
    {
        f>>op>>x>>y;
        if(op==1)
        {
           unite(x,y);
        }
        else
        {
            if(find(x)==find(y))
                g<<"DA\n";
            else g<<"NU\n";
        }
    }
    */
    return 0;
}