#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int n,m,cost,T[200005],r[200005];
struct muchie{
    int x,y,c;
} v[400005];
vector <int> s;

bool func(muchie a,muchie b)
{
    return a.c<=b.c;
}

void Read()
{
    int i;
    in>>n>>m;
    for(i=0;i<m;i++)
        in>>v[i].x>>v[i].y>>v[i].c;
    for(i=1;i<=n;i++)
        T[i]=i;
}

int query(int a,int b)
{
    while(T[a]!=a)
        a=T[a];
    while(T[b]!=b)
        b=T[b];
    if(a==b)
        return 1;
    return 0;
}

void query2(int a,int b)
{
     while(a!=T[a])
    {
        a=T[a];
    }
    while(b!=T[b])
    {
        b=T[b];
    }
    if(r[a]<r[b])
        T[a]=b;
    if(r[a]>r[b])
        T[b]=a;
    if(r[a]==r[b])
    {
        T[a]=b;
        r[b]++;
    }
}

int main()
{
    int i;
    Read();
    sort(v,v+m,func);
    for(i=0;i<m;i++)
    {
        if(query(v[i].x,v[i].y)==0)
        {
            cost+=v[i].c;
            s.push_back(i);
            query2(v[i].x,v[i].y);
        }
    }
    out<<cost<<'\n'<<s.size()<<'\n';
    for(i=0;i<s.size();i++)
        out<<v[s[i]].x<<' '<<v[s[i]].y<<'\n';
    return 0;
}