#include <iostream>
#include<bits/stdc++.h>

using namespace std;

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

const int NMAX=200000;
vector < pair < int , pair < int, int > > > Edge;
vector < pair < int, int > > R;
int n, m, T[NMAX];
long long COST;

void Read()
{
    in>>n>>m;
    int x, y, c;
    for(int i=1; i<=m; i++)
        in>>x>>y>>c, Edge.push_back({x, {y, c}});
}

inline bool COMP(pair < int , pair < int, int > > A, pair < int , pair < int, int > > B)
{
    return A.second.second<B.second.second;
}

inline int Root(int x)
{
    if(T[x]==0)
        return x;
    else
    {
        int k=Root(T[x]);
        T[x]=k;
        return k;
    }

}

void Unite(int x, int y, int c)
{
    int rx=Root(x), ry=Root(y);
    if(rx!=ry)
    {
        T[ry]=rx;
        R.push_back({x, y});
        COST+=c;
    }
}

int main()
{
    Read();
    sort(Edge.begin(), Edge.end(), COMP);
    for(auto it : Edge)
        Unite(it.first, it.second.first, it.second.second);
    out<<COST<<'\n'<<R.size()<<'\n';
    for(auto it : R)
        out<<it.first<<' '<<it.second<<'\n';
    return 0;
}