#include <bits/stdc++.h>

#define pii pair <int, int>
#define piii pair <int, pii>
#define f first
#define s second
#define mp make_pair

using namespace std;

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

const int nMax = 200010;

int t[nMax], lg[nMax];

priority_queue <piii, vector <piii>, greater <piii> > pq;
vector <pii> rasp;

int get_tata(int nod)
{
    if(t[t[nod]] == t[nod]) return t[nod];
    else return t[nod] = get_tata(t[nod]);
}

void unite(int x, int y)
{
    if(lg[x] > lg[y])
    {
        t[y] = x;
        lg[x] += lg[y];
    }
    else
    {
        t[x] = y;
        lg[y] += lg[x];
    }
}

int main()
{
    int n, m; fin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int x, y, z; fin >> x >> y >> z; x--; y--;
        pq.push(mp(z, mp(x, y)));
    }

    for(int i=0; i<n; i++)
    {
        t[i] = i;
        lg[i] = 1;
    }

    int ans = 0;

    while(!pq.empty())
    {
        piii z = pq.top(); pq.pop();
        int c = z.f, x = z.s.f, y = z.s.s;
        int t1 = get_tata(x);
        int t2 = get_tata(y);

        if(t1 == t2) continue;

        unite(t1, t2);

        ans += c;
        rasp.push_back(mp(x, y));
    }

    fout << ans << '\n' << rasp.size() << '\n';
    for(auto it : rasp)
        fout << it.f + 1 << " " << it.s + 1<< '\n';
    return 0;
}