#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int a, b, cost;
};
bool cmp(muchie x, muchie y)
{
    return x.cost<y.cost;
}
int reprezentant(int x,vector<int>&parinte)
{
    if(x==parinte[x])
        return x;
    else return parinte[x]=reprezentant(parinte[x],parinte);
}
void uneste(int a, int b, vector <int> &parinte, vector <int> &adancime)
{
    int rep_a=reprezentant(a,parinte);
    int rep_b=reprezentant(b,parinte);
    if(adancime[rep_a]<adancime[rep_b])
        parinte[rep_a]=rep_b;
    else parinte[rep_b]=rep_a;
    if(adancime[rep_a]==adancime[rep_b])
        adancime[rep_a]++;
}
bool verificare(int a, int b, vector<int>&parinte)
{
    return reprezentant(a,parinte)!=reprezentant(b,parinte);

}
int main()
{
    int n, m;
    f>>n>>m;
    vector<muchie>muchii(m);
    vector <int> parinte(n+1);
    for(int i=1;i<=n;++i)
        parinte[i]=i;
    vector <int> adancime(n+1,0);
    for(int i=0;i<m;i++)
    {
        f>>muchii[i].a>>muchii[i].b>>muchii[i].cost;
    }
    sort(muchii.begin(),muchii.end(),cmp);
    vector< vector<int> >G(n+1);
    int nr=0, cost=0;
    for(auto i:muchii)
    {
        if(verificare(i.a,i.b,parinte))
        {
            uneste(i.a,i.b,parinte,adancime);
            G[i.a].push_back(i.b);
            ++nr;
            cost+=i.cost;
        }
    }
    g<<cost<<"\n"<<nr<<"\n";
    for(int i=1;i<=n;++i)
    {
        for(auto j:G[i])
            g<<i<<" "<<j<<"\n";
    }
    return 0;
}