#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#define NX 200001
#define MX 400001
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct muc
{
    int a,b,c;
};
int n,m;
muc v[MX];
int t[NX];
int total;
vector< pair<int, int> > sol;
 
bool comp(muc a, muc b)
{
    return a.c < b.c;
}
 
void citire()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>v[i].a>>v[i].b>>v[i].c;
    }
 
    for(i=1; i<=n; i++)
    {
        t[i] = i;
    }
}
 
inline int Find(int &x)
{
    if(x == t[x]) return x;
 
    t[x] = Find(t[x]);
    return t[x];
}
 
inline void Union(int &x, int &y)
{
    t[t[x]] = t[y];
}
 
void kruskal()
{
    int i,a,b,c;
    pair<int, int> e;
    for(i=1; i<=m; i++)
    {
        a = v[i].a;
        b = v[i].b;
        c = v[i].c;
 
        if(Find(a) != Find(b))
        {
            Union(a, b);
            total += c;
            e.first = a;
            e.second = b;
            sol.push_back(e);
        }
    }
}
 
int main()
{
    pair<int, int> e;
 
    citire();
 
    sort(v+1, v+m+1, comp);
    kruskal();
 
    fout<<total<<'\n';
    fout<<sol.size()<<'\n';
    while(!sol.empty())
    {
        e = sol.back();
        sol.pop_back();
        fout<<e.first<<' '<<e.second<<'\n';
    }
 
    fin.close(); fout.close();
    return 0;
}