#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream f("kruskal.in");
ofstream g("kruskal.out");
struct muchie
{
    int x, y, c;
    /**bool operator<(muchie m)
    {
        return (c<m.c);
    }*/
};
bool comp(muchie m1, muchie m2)
{
    return (m1.c<m2.c);
}
vector<muchie> G;
vector<int> C;
int nc, n, m, s=0;
void rd()
{
    int i;
    f>>n>>m;
    G.resize(m+1);
    G[0].c=-2000;
    C.resize(n+1);
    for(i=1;i<=m;i++)
        f>>G[i].x>>G[i].y>>G[i].c;
    for(i=1;i<=n;i++)
        C[i]=i;
    nc=n;
}
void Kruskal()
{
    sort(G.begin(), G.end(), comp);
    int i=1, x, y, j;
    while(nc>1)
    {
        while(C[G[i].x]==C[G[i].y])
            G.erase(G.begin()+i);
        x=G[i].x;
        y=G[i].y;
        if(C[x]>C[y])
            swap(x, y);
        for(j=1;j<=n;j++)
        {
            if(j==y)
                continue;
            if(C[j]==C[y])
                C[j]=C[x];
        }
        C[y]=C[x];
        s+=G[i].c;
        i++;
        nc--;
    }
    G.erase(G.begin()+i, G.end());
}
void afis()
{
    g<<s<<'\n';
    g<<G.size()-1<<'\n';
    for(unsigned int i=1;i<G.size();i++)
        g<<G[i].x<<' '<<G[i].y<<'\n';
}
int main()
{
    rd();
    Kruskal();
    afis();
    return 0;
}