#include <iostream>
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define N 200001
struct muchie{

    int c1,c2,cost;
    muchie(int a,int b,int c):c1(a),c2(b),cost(c){};
    muchie(){};
};

vector<muchie> G;
int n,m;
int T[N+1];
int H[N+1];
bool compare(muchie a,muchie b)
{
    return a.cost<b.cost;
}

void citire()
{
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        muchie nou(a,b,c);
        G.push_back(nou);
    }
    sort(G.begin(),G.end(),compare);
}

int findd(int x)
{
    while(T[x]!=x)
        x=T[x];
    return x;
}

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


}

int main()
{
    citire();
    for(int i=1;i<=n;i++)
    {
        T[i]=i;
        H[i]=1;
    }
    int costtot=0,nrmuc(0);
    vector<pair<int,int>> MU;
    for(int i=0;i<G.size();i++)
    {
        if(findd(G[i].c1)!=findd(G[i].c2))
        {
            costtot+=G[i].cost;
            nrmuc++;
            unite(findd(G[i].c1),findd(G[i].c2));
            MU.push_back(make_pair(G[i].c1,G[i].c2));

        }
    }
    g<<costtot<<"\n"<<nrmuc<<"\n";
    for(int i=0;i<MU.size();i++)
        g<<MU[i].first<<" "<<MU[i].second<<endl;

    return 0;
}