#include <bits/stdc++.h>
#include <queue>
#define MAX 200002

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

struct muchie
{
    int x, y;
    int cost;
    friend bool operator >(muchie, muchie);
};
bool operator> (muchie a, muchie b)
{
    return a.cost > b.cost;
}
priority_queue<muchie, vector<muchie>, greater<muchie> > H;

int n, m, x, y, op, costmin, nrsel;
int tata[MAX], h[MAX]; ///h[x] inaltimea arborelui ca rad x
muchie sel[MAX];

int Find(int x); ///returneaza radacina arborelui din care face parte x
void Union(int x, int y); ///reuneste arborele din care face parte x cu arborele din care face parte y
void citire();
void Kruskal();
void afisare();
int main()
{
    citire(); ///MIN HEAP ul este creat
    Kruskal();
    afisare();
    /*fin >> n >> m;
    for(i = 1;i<=m;i++)
    {
        fin >> op >> x >> y;
        if(op == 1)
            Union(x, y);
        else {
            if(Find(x) == Find(y)) fout << "DA" << '\n';
            else fout << "NU" << '\n';
        }
    }*/
    return 0;
}
void Kruskal()
{
    muchie a;
    int c1, c2;
    while(nrsel < n - 1)
    {
        a = H.top();
        H.pop();
        c1 = Find(a.x);
        c2 = Find(a.y);
        if(c1 != c2)
        {
            sel[nrsel++] = a;
            costmin += a.cost;
            Union(c1, c2);
        }
    }
}
void afisare()
{
    int i;
    fout << costmin << '\n' << n-1 << '\n';
    for(i=0;i<nrsel;i++)
        fout << sel[i].x << ' ' << sel[i].y << '\n';
}
void citire()
{
    muchie a;
    int i;
    fin >> n >> m;
    for(i = 1 ;i <= m; i++)
    {
        fin >> a.x >> a.y >> a.cost;
        H.push(a);
    }
}
int Find(int x)
{
    int rad, y;
    rad = x;
    while(tata[rad] != 0)
        rad = tata[rad];

    ///COMPRESEZ DRUMUL
    while(tata[x])
    {
        y = tata[x];
        tata[x] = rad;
        x = y;
    }
    return rad;
}
void Union(int x, int y)
{
    int a, b;
    a = Find(x); //rad x
    b = Find(y); //rad y
    if(h[a] > h[b])
        tata[b] = a;
    else {
            tata[a] = b;
            if(h[a] == h[b]) h[b]++;
    }
}