#include <bits/stdc++.h>
#define Max 400001
using namespace std;

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

pair <int, int> P[Max];
int N, M, Total, TT[Max], RG[Max];
int k;
struct Edge
{
    int x, y, weigh;
}v[Max];

struct Compare
{
    bool operator()(Edge x, Edge y)
    {
        return x.weigh < y.weigh;
    }
};
void Read()
{
    fin >> N >> M;
    for (int i=1; i<=M; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].weigh;
    }
}
int Find(int Node)
{
    while (TT[Node] != Node)
    {
        Node = TT[Node];
    }
    return Node;
}
void Unite(int x, int y)
{
    if (RG[x] < RG[y])
        TT[x] = y;
    if (RG[x] > RG[y])
        TT[y] = x;
    if (RG[x] == RG[y])
    {
        TT[x] = y;
        RG[y]++;
    }
}
void Kruskal()
{
    sort(v+1, v+M+1, Compare());
    for (int i=1; i<=N; i++)
    {
        TT[i] = i;
        RG[i] = 1;
    }
    for (int i=1; i<=M; i++)
    {
        int tata_x=Find(v[i].x);
        int tata_y=Find(v[i].y);
        if (tata_x != tata_y)
        {
            Unite(tata_x, tata_y);
            P[++k].first=v[i].x;
            P[k].second=v[i].y;
            Total += v[i].weigh;
        }
    }
}
void Write()
{
    fout << Total << '\n';
    fout << N-1 << '\n';
    for (int i=1; i<=k; i++)
        fout << P[i].second << " " << P[i].first << '\n';
}
int main()
{
    Read();
    Kruskal();
    Write();
    return 0;
}