#include<iostream>
#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int gr[500000],x[500000],y[500000],cost[500000];
int n,m,suma,ind[500000];
vector<int> v;
int grupa(int i)
{
    if (gr[i] == i) return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}
void reuniune(int i,int j)
{
    gr[grupa(i)] = grupa(j);
}
bool comp(int i,int j)
{
    return(cost[i] < cost[j]);
}
 
int main()
{   f>>n>>m;
    for(int i = 1;i <= m;++i)
    {   f>>x[i]>>y[i]>>cost[i];
        ind[i] = i;
    }
    for(int i = 1;i <= n; ++i) gr[i] = i;
    sort(ind + 1,ind + m + 1,comp);
    for(int i = 1;i <= m; ++i)
    {   if (grupa(x[ind[i]])!= grupa(y[ind[i]]))
        {   suma+=cost[ind[i]];
            reuniune(x[ind[i]],y[ind[i]]);
            v.push_back(ind[i]);
        }
    }
    g<<suma<<'\n'<<n-1<<'\n';
    for(int i = 0;i < n - 1; ++i)
        g<<y[v[i]]<<" "<<x[v[i]]<<'\n';
    return 0;
}