#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define nmax 200005
#define mmax 400005

using namespace std;

struct graf {
    int nod, vecin, cost;
} G[nmax];

FILE *fi, *fo;

int n, m, k, rez, l;
int T[nmax], NR[nmax];

vector < pair<int, int> > s;

bool cmp(graf a, graf b)
{
    return a.cost < b.cost;
}

int root(int nod)
{
    if (T[nod] == nod)
        return nod;
    return root(T[nod]);
}

int main()
{
    
    fi = fopen("apm.in", "r");
    fo = fopen("apm.out", "w");
    
    fscanf(fi, "%d%d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        T[i] = i, NR[i] = 1;
    
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        fscanf(fi, "%d%d%d", &x, &y, &z);
        G[++k].nod = x, G[k].vecin = y, G[k].cost = z;
        G[++k].nod = y, G[k].vecin = x, G[k].cost = z;
    }
    
    sort(G+1, G+k+1, cmp);
    
    for (int i = 1; i <= k; i++)
    {
        int p1 = root(G[i].nod);
        int p2 = root(G[i].vecin);
        int c = G[i].cost;
        
        if (p1 == p2)
            continue;
       
        if (NR[p1] >= NR[p2])
        {
            NR[p1] += NR[p2];
            T[p2] = p1;
        }
        else
        {
            NR[p2] += NR[p1];
            T[p1] = p2;
        }
        
        if (l == n - 1)
            break;
        
        rez += c;
        ++l;
        s.push_back(make_pair(G[i].nod, G[i].vecin));
        
    }
    
    fprintf(fo, "%d\n", rez);
    fprintf(fo, "%d\n", int(s.size()));
    for (int i = 0; i < int(s.size()); i++)
        fprintf(fo, "%d %d\n", s[i].first, s[i].second);
    
    fclose(fi);
    fclose(fo);
    
    return 0;
}