#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 200005

using namespace std;

int tati[200005],suma,n,m;

struct nod
{
    int x;
    int y;
    int cost;
    void cit()
    {
        scanf(" %d %d %d", &x, &y,&cost);
    }
}g;

bool cmp(nod a, nod b)
{
    return (a.cost<b.cost);
}

vector < nod > graf;
vector <pair <int,int> >sol;

int adaug(int x)
{
    if(tati[x]==0)
       return x;
    tati[x]=adaug(tati[x]);
    return tati[x];
}

int verificare(int x,int y)
{
    int dx=adaug(x);
    int dy=adaug(y);
    if(dx==dy)
        return 1;
    return 0;
}

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=0;i<m;i++)
    {
        g.cit();
        graf.push_back(g);
    }
    sort(graf.begin(),graf.end(),cmp);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    for(nod i: graf)
    {
        if(!verificare(i.x,i.y))
            {
                suma+=i.cost;
                sol.push_back({i.x,i.y});
                tati[adaug(i.x)]=adaug(i.y);
            }
    }
    cout<<suma<<"\n";
    cout<<sol.size()<<"\n";
    for(auto i:sol)
        cout<<i.first<<" "<<i.second<<"\n";
    return 0;
}