#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
const int NMAX = 200005;
int t[NMAX] , h[NMAX];
struct ROOTS{
int x,y,cost;
};
vector<ROOTS>r;
vector<ROOTS>p;
bool cmp(ROOTS a,ROOTS b)
{
    return a.cost < b.cost;
}
int FindSet(int x)
{
    while(x != t[x])
        x = t[x];
    return x;
}
void UnionSet(int x,int y)
{
    if(h[x] == h[y])
    {
        h[x]++;
        t[y] = x;
    }
    else if(h[x] < h[y])
        t[x] = y;
    else
        t[y] = x;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n , m , x , y , cost;
    ROOTS temp;
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; i++)
    {
        h[i] = 1;
        t[i] = i;
    }
    for(int i = 1 ; i <= m  ;i++)
    {
        scanf("%d%d%d",&x,&y,&cost);
        temp.x = x;
        temp.y = y;
        temp.cost = cost;
        r.push_back(temp);
    }
    sort(r.begin(),r.end(),cmp);
    int costul = 0 , numarul = 0;
    for(int i = 0 ; i < r.size(); i++)
    {
        int cx = FindSet(r[i].x);
        int cy = FindSet(r[i].y);
        if(cx != cy)
            {
                UnionSet(cx,cy);
                costul += r[i].cost;
                temp = r[i];
                p.push_back(temp);
            }
    }
    printf("%d\n%d\n",costul,p.size());
    for(int i = 0 ; i < p.size() ; i++)
        printf("%d %d\n",p[i].y,p[i].x);
    return 0;
}