#include <bits/stdc++.h>

using namespace std;

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

int n,m,T[200002],rang[200002];

struct muchie
{
    int x,y,c;

    bool operator < (muchie & other)
    {
        return c < other.c;
    }
};
vector<muchie>v;

int Rad(int nod)
{
    if(T[nod]==0)
        return nod;
    else
    {
        int x;
        x=Rad(T[nod]);
        T[nod]=x;

        return x;
    }

}

void unire(int a, int b)
{
    if(rang[a] > rang[b])
    {
        T[b]=a;
    }
    else
    {
        T[a]=b;
        if(rang[a] == rang[b])
            rang[b]++;

    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        fin>>x>>y>>c;
        v.push_back({x,y,c});
    }

    sort(v.begin(),v.end());

    long long cost=0;
    vector<pair<int,int>>m;
    for(auto it : v)
    {
        int rx=Rad(it.x);
        int ry=Rad(it.y);
        if(rx != ry)
        {
            cost+=it.c;
            m.push_back({it.x,it.y});
            unire(rx,ry);
        }
    }

    fout<<cost<<'\n';
    fout<<m.size()<<'\n';
    for(auto it : m)
        fout<<it.first<<' '<<it.second<<'\n';
}