#include <bits/stdc++.h>
#define NMAX 200002
#define MMAX 400002

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

struct mch
{
    int x, y, c;
};

int n, m;
int tata[NMAX];
long long apm;

vector <mch> muchii;
vector <mch> afis;

int union_find(int x);
void union_merge(int a, int b);
void apm_kruskal();
bool csort(mch a, mch b)
{
    return a.c < b.c;
}

int main()
{
    fin >> n >> m;
    mch arc;
    while(fin >> arc.x >> arc.y >> arc.c)
        muchii.push_back(arc);

    apm_kruskal();

    fout << apm << '\n';
    fout << afis.size() << '\n';
    for(auto i : afis)
        fout << i.x << ' ' << i.y << '\n';

    return 0;
}

void apm_kruskal()
{
    int i;
    ///initializare
    for(i = 1; i <= n; i++)
        tata[i] = i;
    sort(muchii.begin(), muchii.end(), csort);

    ///kruskal
    for(auto i : muchii)
        if(union_find(i.x) != union_find(i.y))
        {
            apm += i.c;
            union_merge(i.x, i.y);
            afis.push_back(i);
        }
}

///colapseaza lista de parents
int union_find(int x)
{
    if(tata[x] == x)
        return x;
    else
        return tata[x] = union_find(tata[x]);
}

///da merge (va fi colapsat inevitabil urm data cand este apelat union_find() - veri cul)
void union_merge(int a, int b)
{
    a = union_find(a);
    b = union_find(b);

    if(a != b)
        tata[b] = a;
}