#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct el
{
    int x,y,c;
};
el v[200001];
int n,m,a,b,sum,i,t[200001];
vector <int> sol;
int cmp (const el &a,const el &b)
{
    if (a.c==b.c)
    {
        if (a.x==b.x)
            return a.y<b.y;
        return a.x<b.x;
    }
    return a.c<b.c;
}
int f (int x)
{
    if (x==t[x])
        return x;
    return t[x]=f (t[x]);
}
void join (int x,int y)
{
    a=f (x);
    b=f (y);
    if (a==b)
        return ;
    t[a]=b;
}
int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    for (i=1; i<=n; i++)
        t[i]=i;
    sort (v+1,v+m+1,cmp);
    for (i=1; i<=m; i++)
    {
        if (f (v[i].x)!=f (v[i].y))
        {
            sum+=v[i].c;
            sol.push_back (i);
            join (v[i].x,v[i].y);
        }
    }
    fout<<sum<<"\n"<<sol.size ()<<"\n";
    for (i=0; i<sol.size (); i++)
        fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
    return 0;
}