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

using namespace std;

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

int n, m;

struct truple
{
    int a, b, c;
    bool ex;
};

bool cmp(truple a, truple b)
{
    return a.c < b.c;
}
int find_tata(int nod, vector < pair <int, int> > &tata)
{
    if(tata[nod].first==nod)
        return nod;
    return find_tata(tata[nod].first, tata);
}
int main()
{
    int costTotal = 0;
    vector <truple> muchii;
    vector < pair <int, int> > tata;
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int v, u, w;
        fin>>v>>u>>w;
        muchii.push_back(truple());
        muchii[i].a=v;
        muchii[i].b=u;
        muchii[i].c=w;
    }
    sort(muchii.begin(), muchii.end(), cmp);
    tata.resize(n+1);
    for(int i=1; i<=n; i++)
        tata[i].first=i;

    for(int i=0; i<m; i++)
    {
        int ta, tb;
        ta = find_tata(muchii[i].a, tata);
        tb = find_tata(muchii[i].b, tata);
        if(ta!=tb)
        {
            tata[ta].first=tb;
            muchii[i].ex = 1;
            costTotal += muchii[i].c;
        }
    }
    fout<<costTotal<<'\n'<<n-1<<'\n';
    for(int i=0; i<m; i++)
        if(muchii[i].ex)
            fout<<muchii[i].a<<' '<<muchii[i].b<<'\n';
    return 0;
}