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

using namespace std;

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

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;
	else
        return find_tata(tata[nod].first, tata);
}

void unire_arbori(int v, int u, vector<pair<int, int>> &tata)
{
	if(tata[v].second>tata[u].second)
		tata[u].first=v;
	else
        if(tata[v].second<tata[u].second)
            tata[v].first=u;
        else
        {
            tata[u].first=v;
            tata[v].second++;
        }
}

int main()
{
    int n, m, 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;
    int i=0, k=0;
    while(k<n-1)
    {
        int ta, tb;
        ta = find_tata(muchii[i].a, tata);
        tb = find_tata(muchii[i].b, tata);
        if(ta!=tb)
        {
            muchii[i].ex = 1;
            costTotal+=muchii[i].c;
            unire_arbori(ta, tb, tata);
            k++;
        }
        i++;
    }
    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;
}