#include <bits/stdc++.h>
using namespace std;

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

struct muchii
{
    int x , y , cost , ales;
};
muchii a[400005];
int n , m , t[200005] , costTot , nrc;

bool Comp(muchii q , muchii p)
{
    return q.cost < p.cost;
}

void Union(int x , int y)
{
    t[y] = x;
}

int Find(int x)
{
    int rad = x , aux;
    while(t[rad] != 0)
        rad = t[rad];
    while(x != rad)
    {
        aux = x;
        t[x] = rad;
        x = t[aux];
    }
    return rad;
}

void Kruskal()
{
    int i , j , k , cnt = n;
    sort(a + 1 , a + m + 1 , Comp);
    for(k = 1;k <= m and cnt > 1;k++)
    {
        i = Find(a[k].x);
        j = Find(a[k].y);
        if(i != j)
        {
            Union(i , j);
            cnt--;
            nrc++;
            costTot += a[k].cost;
            a[k].ales = 1;
        }
    }
}

int main()
{
    int i, k;
    fin >> n >> m;
    for(k = 1;k <= m;k++)
        fin >> a[k].x >> a[k].y >> a[k].cost;
    Kruskal();
    fout << costTot << "\n" << nrc << "\n";
    for(i = 1;i <= m;i++)
        if(a[i].ales == 1) fout << a[i].y << " " << a[i].x << "\n";
    return 0;
}