#include <fstream>
#include <algorithm>

using namespace std;

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

struct muchie{
    int x, y;
    int cost;
}M[400005];

int n, m, lg;
int p[200005];
int N1[200005], N2[200005], heap[200005];

void Union(int poz1, int poz2)
{
    p[poz1] = poz2;
}

int rad(int poz)
{
    if(p[poz] != poz)
        return rad(p[poz]);
    else
        return poz;
}
/*bool functie(muchie a, muchie b)
{
    return a.cost < b.cost;
 */

void urca(int poz)
{
    if(poz/2 >= 1)
        if(heap[poz] < heap[poz/2])
            {
                swap(heap[poz], heap[poz/2]);
                swap(N1[poz], N1[poz/2]);
                swap(N2[poz], N2[poz/2]);
                urca(poz/2);
            }
}
void adauga(int n1, int n2, int c)
{
    lg++;
    heap[lg] = c;
    N1[lg] = n1;
    N2[lg] = n2;
    urca(lg);
}

void coboara(int poz)
{
    int poz_min;
    if(lg < poz*2)
        return;
    if(heap[poz*2] < heap[poz*2+1] || lg == poz*2)
        poz_min = poz*2;
    else
        poz_min = poz*2 + 1;
    if(heap[poz] > heap[poz_min])
    {
        swap(heap[poz], heap[poz_min]);
        swap(N1[poz], N1[poz_min]);
        swap(N2[poz], N2[poz_min]);
        coboara(poz_min);
    }
}
void scoate(int cnt)
{
    M[cnt].x = N1[1];
    M[cnt].y = N2[1];
    M[cnt].cost = heap[1];
    N1[1] = N1[lg];
    N2[1] = N2[lg];
    heap[1] = heap[lg];
    lg--;
    coboara(1);

}
int cnt;
long long suma;
int v[400005];
int n1, n2, c;

int main()
{
    cin >> n;
    cin >> m;
    for(int i = 1; i <= n; i++)
        p[i]=i;
    for(int i = 1; i <= m; i++)
    {
        //cin >> M[i].x >> M[i].y >> M[i].cost;
        cin >> n1 >> n2 >> c;
        adauga(n1,n2,c);
    }
    for(int i = 1; i <= m; i++)
        scoate(i);
   // sort(M+1, M+m+1, functie);
    int poz = 1;
    while(cnt < n-1)
    {
        if(rad(M[poz].x) != rad(M[poz].y))
        {
            Union(M[poz].x,M[poz].y);
            cnt++;
            suma += M[poz].cost;
            v[cnt] = poz;
        }
        poz++;
    }
    cout << suma<<'\n'<<cnt<<'\n';
    for(int i = 1; i <= cnt; i++)
    {
        int a = v[i];
        cout << M[a].x<<' '<<M[a].y<<'\n';
    }
    return 0;
}