#include <bits/stdc++.h>
#define inf 2000000

using namespace std;

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

struct muchie
{
    int x,y,c;
    bool operator < (muchie & other)
    {
        return c < other.c;
    }
};

vector<muchie>v;



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

int Rad(int nod)
{
    if(T[nod]==0)
        return nod;
    else
    {
        int 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());

    int cost=0;
    vector<pair<int,int>>rasp;

    for(auto it : v)
    {
        int rx,ry;
        rx=Rad(it.x);
        ry=Rad(it.y);
        if(rx!=ry)
        {
            rasp.push_back({it.x,it.y});
            cost+=it.c;
            unire(rx,ry);
        }
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(auto it : rasp)
        fout<<it.first<<' '<<it.second<<'\n';
}