#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN 200010

using namespace std;

struct vecin
{
    int x, y, cost;
    vecin(int x=0, int y=0, int cost=0):x(x), y(y), cost(cost)
    {

    }
    bool operator()(vecin a, vecin b)
    {
        return a.cost > b.cost;
    }
};

priority_queue<vecin, vector<vecin>, vecin> q;
vector<vecin> v[MAXN];
vector<vecin> muchii; // y=>x, cost=>y
int arbore[MAXN], nrn, ctot;
int n, m;

void citire()
{
    int x, y, c;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        v[x].push_back(vecin(x, y, c));
        v[y].push_back(vecin(y, x, c));
    }
}

void adaugVecini(int x)
{
    for (int i = 0; i < v[x].size(); i++)
        q.push(v[x][i]);
}

void solve()
{
    arbore[1] = 1; nrn = 1;
    adaugVecini(1);
    while (!q.empty() && nrn < n)
    {
        vecin top = q.top();
        q.pop();
        if (arbore[top.y])
            continue;
        arbore[top.y] = 1;
        ++nrn;
        ctot += top.cost;
        muchii.push_back(top);
        adaugVecini(top.y);
    }
}

void afisare()
{
    printf("%d\n", ctot);
    printf("%d\n", muchii.size());
    for (int i = 0; i < muchii.size(); i++)
        printf("%d %d\n", muchii[i].x, muchii[i].y);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    citire();
    solve();
    afisare();

    return 0;
}