#include <bits/stdc++.h>

using namespace std;

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

struct nod
{
    int x, y, c;
    bool operator < (const nod &other) const
    {
        return c<other.c;
    }
};

int n, m, cost, viz[200041], height[200041], nr;
vector <nod> M, sol;

void read()
{
    fin >> n >> m;
    int x, y, c;
    for (int i=0;i<m;++i)
    {
        fin >> x >> y >> c;
        M.push_back({y,x,c});
        M.push_back({x,y,c});
    }
    sort (M.begin(),M.end());
    for (int i=1;i<=n;++i)
        viz[i]=i;
}

int fnd(int x)
{
    if (x!=viz[x])
        return fnd(viz[x]);
    return viz[x];
}

void uni(int a, int b)
{
    a=fnd(a);
    b=fnd(b);
    if (height[a]>height[b])
        viz[b]=a;
    else
        viz[a]=b;
    if (height[a]==height[b])
        height[b]++;
}

void kruskal()
{
    for (int i=0;i<M.size();++i)
    {
        if (fnd(M[i].x)!=fnd(M[i].y))
        {
            uni(M[i].x,M[i].y);
            cost+=M[i].c;
            nr++;
            sol.push_back(M[i]);
        }
    }
}

int main()
{
    read();
    kruskal();
    fout << cost << "\n" << nr << "\n";
    for (int i=0;i<nr;++i)
    {
        fout << sol[i].x << " " << sol[i].y << "\n";
    }
    return 0;
}