#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct graf
{
    int x, y, c;
};
vector < graf > v;
int radacina[200002];
int grupa (int i)
{
    if(i==radacina[i]) return i;
    radacina[i]=grupa(radacina[i]);
    return radacina[i];
}
void uneste (int x, int y)
{
    radacina[grupa(x)]=grupa(y);
}
bool cresc (const graf &a, const graf &b)
{
    return a.c<b.c;
}
vector < pair < int , int > > sol;
int mx=0;
int n,m,x,y,c;
void kruskal ()
{
    sort(v.begin(),v.end(),cresc);
    for(int i=1; i<=n; i++)
        radacina[i]=i;
    for(int i=0; i<m; i++)
    {
        x=v.at(i).x;
        y=v.at(i).y;
        c=v.at(i).c;
        if(grupa(x)!=grupa(y))
        {
            uneste(x,y);
            mx+=c;
            sol.push_back({x,y});
        }
    }
}
int main()
{
    in>>n>>m;
    for(int i=0; i<m; i++)
    {
        in>>x>>y>>c;
        v.push_back({x,y,c});
    }
    kruskal();
    out<<mx<<'\n';
    m=sol.size();
    out<<m<<'\n';
    for(int i=0; i<m; i++)
        out<<sol.at(i).first<<' '<<sol.at(i).second<<'\n';
    return 0;
}