#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
struct muchie
{
    int x;
    int y;
    int c;
};
muchie g[400005];
bool fcmp(muchie a,muchie b)
{
    if(a.c < b.c)
        return true;
    return false;
}
int f[200005];
int rang[200005];
int radacina(int nod)
{
    int rasp = nod;
    while(f[rasp]!=rasp)
        rasp = f[rasp];
    while(f[nod]!=nod)
    {
        int aux = f[nod];
        f[nod] = rasp;
        nod = aux;
    }
    return rasp;
}
void uneste(int x,int y)
{
    if(rang[x]>rang[y])
        f[y] = x;
    else if (rang[y] > rang[x])
        f[x] = y;
    else
    {
        rang[x]++;
        f[y] = x;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> m;
    int sum  = 0;
    vector < pair<int,int> > rasp;
    for(int i=1;i<=m;i++)
        cin >> g[i].x >> g[i].y >> g[i].c;
    for(int i=1;i<=n;i++)
    {
        f[i] = i;
        rang[i] = 1;
    }
    sort(g+1,g+m+1,fcmp);
    for(int i=1;i<=m;i++)
    {
        int x = g[i].x;
        int y = g[i].y;
        int c = g[i].c;
        x = radacina(x);
        y = radacina(y);
        if(x==y)
            continue;
        sum = sum + c;
        rasp.push_back({g[i].x,g[i].y});
        uneste(x,y);
    }
    cout << sum << '\n';
    cout << rasp.size() << '\n';
    for(auto x:rasp)
        cout << x.first << ' ' << x.second << '\n';
    return 0;
}