#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200002
#define mmax 400004
using namespace std;
ifstream is ("apm.in");
ofstream os ("apm.out");

vector< pair<int,int> >ANS;
int X[mmax], Y[mmax], C[mmax], IND[mmax], GR[nmax];
int N, M, ANSW;
struct Comp{
    bool operator()(const int& x, const int& y){
        return (C[x] < C[y]);
    }
};

void Read();
void Solve();
int Group(int);
void Union(int,int);

int main()
{
    Read();
    Solve();
    os << ANSW << "\n" << ANS.size() << "\n";
    vector<pair<int,int> >::iterator it;
    for(it = ANS.begin(); it != ANS.end(); ++it)
        os << it->first << " " << it->second << "\n";
    is.close();
    os.close();
    return 0;
}
void Read()
{
    int x, y, c;
    is >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        is >> x >> y >> c;
        X[i] = x;
        Y[i] = y;
        C[i] = c;
        IND[i] = i;
    }
    for(int i = 1; i <= N; ++i)
        GR[i] = i;
    sort(IND+1, IND+M+1, Comp());
}
void Solve()
{
    int x;
    for(int i = 1; i <= M; ++i)
    {
        x = IND[i];
        if(Group(X[x]) != Group(Y[x]))
        {
            ANSW += C[x];
            ANS.push_back({X[x], Y[x]});
            Union(X[x], Y[x]);
        }
    }
}
int Group(int x)
{
    if(GR[x] == x)
        return x;
    GR[x] = Group(GR[x]);
    return GR[x];
}
void Union(int x, int y)
{
    GR[Group(y)] = Group(x);
}