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

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct muchie
{
    int x,y,c;
    bool operator<(const muchie& alta)
    {
        return c<alta.c;
    }
};
int nrmuchii=0,cost=0;
vector<int>rang,T;
vector<pair<int,int>>sol;
vector<muchie>G;
int N,M;

int radacina(int x)
{
    if(T[x]==0)
        return x;
    return radacina(T[x]);
}

void unite(int a,int b)
{
    if(a!=b)
    {
        if(rang[a]<rang[b])
            T[a]=b;
        else
        {
            if(rang[a]==rang[b])
                rang[a]++;
            T[b]=a;
        }
    }
}

void kruskal()
{
    for(auto&i:G)
    {
        int a=radacina(i.x),b=radacina(i.y);
        if(a!=b)
        {
            unite(a,b);
            nrmuchii++;
            cost+=i.c;
            sol.push_back({i.x,i.y});
        }
        if(nrmuchii==N-1)
            break;
    }

}

int main()
{
    cin>>N>>M;
    T=rang=vector<int>(N+1,0);
    for(int i=0; i<M; i++)
    {
        int x,y,c;
        cin>>x>>y>>c;

        G.push_back({x,y,c});
    }
    sort(G.begin(),G.end());
    kruskal();
    cout<<cost<<'\n'<<nrmuchii<<'\n';
    for(auto&i:sol)
    {
        cout<<i.second<<" "<<i.first<<'\n';
    }
    return 0;
}