#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct Muchie{
    int v1,v2,cost;
    Muchie(int x, int y, int c)
    {
        v1 = x;
        v2 = y;
        cost = c;
    }
};
bool comp(Muchie &m1, Muchie &m2)
{
    return m1.cost < m2.cost;
}
vector<int> tata;
vector<Muchie> muchii,rez;
int reprez(int i)
{
    if(tata[i]!=i)
        tata[i] = reprez(tata[i]);
    return tata[i];
}
int main()
{
    int n,m,cost_total=0;
    cin>>n>>m;
    tata.resize(n+1);
    for(int i=1;i<=n;i++)
        tata[i] = i;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        muchii.push_back(Muchie(x,y,c));
    }
    sort(muchii.begin(),muchii.end(),comp);
    for(int i=0;i<m;i++)
    {
        int vf1 = muchii[i].v1;
        int vf2 = muchii[i].v2;
        int r1 = reprez(vf1);
        int r2 = reprez(vf2);
        if(r1!=r2)
        {
            rez.push_back(muchii[i]);
            cost_total+=muchii[i].cost;
        }
    }
    cout<<cost_total<<'\n'<<rez.size()<<'\n';
    for(Muchie m:rez)
        cout<<m.v1<<' '<<m.v2<<'\n';
    return 0;
}