#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x, y, c;
};
struct cmp{
    bool operator () (const muchie & A, const muchie & B) const
    {
        return A.c < B.c;
    }
};

muchie Muchii[400002];
int grupa[200002];
vector <pair<int,int>> Ans;
int N, M;

int multime(int x)
{
    int tata_x = grupa[x];
    for (; x != tata_x; x = tata_x, tata_x = grupa[tata_x])
        ;
    for (; x != grupa[x]; x = grupa[x])
        grupa[x] = tata_x;
    return tata_x;
}
void uneste(int x, int y)
{
    grupa[multime(y)] = multime(x);
}


int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
        f >> Muchii[i].x >> Muchii[i].y >> Muchii[i].c;
    sort (Muchii + 1, Muchii + M + 1, cmp());
    for (int i = 1; i <= N; ++i)
        grupa[i] = i;
    int ans = 0;
    for (int i = 1; i <= M; ++i)
        if (multime(Muchii[i].x) != multime(Muchii[i].y))
        {
            ans += Muchii[i].c;
            uneste(Muchii[i].x, Muchii[i].y);
            Ans.push_back({Muchii[i].x, Muchii[i].y });
        }
    g << ans << "\n";
    g << N - 1 << "\n";
    for (const pair <int,int> & x : Ans)
        g << x.first << " " << x.second << "\n";
    f.close();
    g.close();
    return 0;
}