#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <climits>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x, y, c;
    bool operator<(muchie m)
    {
        return(c<m.c);
    }
};
vector<muchie> G;
vector<int> t;
int nc, n, m, j, c, cst;
void rd()
{
    f>>n>>m;
    G.resize(m);
    t.resize(n+1);
    for(int i=0;i<m;i++)
        f>>G[i].x>>G[i].y>>G[i].c;
    for(int i=1;i<=n;i++)
        t[i]=i;
}
int tata(int x)
{
    if(t[x]!=x)
        t[x]=tata(t[x]);
    return t[x];
}
inline void unite(int x, int y)
{
    t[tata(x)]=tata(y);
}
inline bool q(int x, int y)
{
    int r=tata(x);
    return(r==tata(y));
}
void Kruskal()
{
    vector<muchie>::iterator i=G.begin();
    nc=n;
    sort(G.begin(), G.end());
    while(nc>1)
    {
        while(q(i->x, i->y))
            G.erase(i);
        unite(i->x, i->y);
        cst+=i->c;
        i++;
        nc--;
    }
    G.erase(i, G.end());
}
void afis()
{
    g<<cst<<'\n'<<G.size()<<'\n';
    for(auto a:G)
        g<<a.x<<' '<<a.y<<'\n';
}
int main()
{
    rd();
    Kruskal();
    afis();
    return 0;
}