#include <bits/stdc++.h>
using namespace std;
const int NMAX = 400001;
pair<int, int> A[NMAX];
int T[NMAX],R[NMAX],n,m,k,ct;
struct edge{
    int x,y,w;
} G[NMAX];
ifstream f("apm.in");
ofstream g("apm.out");
void citire(){
    f>>n>>m;
    for (int i=1;i<=m;i++)
    {
        f>>G[i].x>>G[i].y>>G[i].w;
    }
}
int find(int x)
{
    while (T[x] != x)
    {
        x = T[x];
    }
    return x;
}
void Union(int x, int y){
    if (R[x] < R[y])
    {
        T[x]=y;
    }
    if (R[x] > R[y])
    {
        T[y]=x;
    }
    if (R[x]==R[y])
    {
        T[x]=y;
        R[y]++;
    }
}
void Kruskal()
{
    for (int i=1;i<=m;i++)
    {
        int tx,ty;
        tx = find(G[i].x);
        ty = find(G[i].y);

        if (tx != ty)
        {
            Union(tx, ty);
            A[++k].first = G[i].x;
            A[k].second = G[i].y;
            ct+=G[i].w;
        }
    }
}
bool cmp(edge e1, edge e2)
{
    return e1.w < e2.w;
}
int main()
{
    citire();
    sort(G+1,G+m+1,cmp);
    for (int i=1;i<=n;i++)
    {
        T[i]=i;
        R[i]=1;
    }
    Kruskal();
    g<<ct<<"\n"<<n-1<<"\n";
    for (int i=1;i<n;i++)
    {
        g<<A[i].second<<" "<<A[i].first<<"\n";
    }
    f.close();
    g.close();
    return 0;
}