#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax=200005, mmax=400005;
int n, m;
int father[nmax], answer[mmax][3];

struct graph
{
    int x,y,c;
}g[nmax];

void read_data()
{
    int i;

    fin>>n>>m;

    for(i=1;i<=m;i++)
        fin>>g[i].x>>g[i].y>>g[i].c;
}
bool cmp(graph a, graph b)
{
    return a.c<b.c;
}
inline int root(int node)
{
    while(father[node]!=node)
        node=father[node];

    return node;
}
void kruskal()
{
    int i, edges=0, cost=0, K=0, root_x, root_y;

    sort(g+1,g+m+1,cmp);

    for(i=1;i<=n;i++)
        father[i]=i;

    i=1;

    while(edges<n-1)
    {
        root_x=root(g[i].x);
        root_y=root(g[i].y);

        if(root_x!=root_y)
        {
            edges++;
            cost+=g[i].c;

            father[root_x]=root_y;

            K++;
            answer[K][1]=g[i].x;
            answer[K][2]=g[i].y;
        }

        i++;
    }

    fout<<cost<<'\n';
    fout<<edges<<'\n';

    for(i=1;i<=K;i++)
        fout<<answer[i][1]<<' '<<answer[i][2]<<'\n';
}
int main()
{
    read_data();
    kruskal();
}