#include <cstdio>
#include <vector>
#include <algorithm>
#define MMAX 400100
using namespace std;

FILE *f = freopen("apm.in", "r", stdin);
FILE *g = freopen("apm.out", "w", stdout);


int Father[MMAX];
int N, M, C_sol;
struct muchie{
    int a, b, cost;

    muchie(int &a, int &b, int &cost)
    {
        this -> a = a;
        this -> b = b;
        this -> cost = cost;
    }
    bool operator < (const muchie &mc) const {
        return this -> cost < mc.cost;
    }
};
struct sol{
    int x, y;
};
vector <muchie> candidate;
vector <sol> ANS;
int find_(int x)
{
    while(x != Father[x])
        x = Father[x];
    return x;
}
void unite_(int x, int y)
{
    Father[find_(x)] = find_(y);
}
void read()
{
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=M; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        candidate.push_back(muchie(x, y, z));
    }
    for(int i = 1; i<=N; i++)
        Father[i] = i;
}
void solve()
{
    sort(candidate.begin(), candidate.end());
    for(int i = 0; i<M; i++)
    {
        muchie muc = candidate[i];
        int x = find_(muc.a);
        int y = find_(muc.b);
        if(x != y) {
            unite_(muc.a, muc.b);
            C_sol += candidate[i].cost;
            sol rez;
            rez.x = muc.a;
            rez.y = muc.b;
            ANS.push_back(rez);
        }
    }
}
void write()
{
    printf("%d\n%d\n", C_sol, N - 1);
    for(int i = 0; i<ANS.size(); ++i)
        printf("%d %d\n", ANS[i].x, ANS[i].y);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}