#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
#define N 200005

using namespace std;

struct nod
{
    int x, y, c;
}nou;

int t[N];
vector <nod> graf, sol;
vector <nod> ::iterator  it;
int n, m, s;

int cmp(nod x, nod y)
{
    return (x.c<y.c);
}

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d\n", &nou.x, &nou.y, &nou.c);
        graf.push_back(nou);
    }
    sort(graf.begin(), graf.end(), cmp);
}

void adaug(int x, int y)
{
    if(t[x]!=t[y])
    {
        int r1=t[x], r2=t[y], nr1=0, nr2=0;
        while(r1!=t[r1])
                r1=t[r1], nr1++;
        while(r2!=t[r2])
                r2=t[r2], nr2++;
        if(nr1<nr2)
            t[r1]=r2;
        else
            t[r2]=r1;
    }
}

int multime(int x, int y)
{
    int r1=t[x], r2=t[y];
    while(r1!=t[r1])
            r1=t[r1];
    while(r2!=t[r2])
            r2=t[r2];
    return (r1==r2);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    citire();
    for(int i=1;i<=n;i++)
        t[i]=i;
    for(it=graf.begin();it!=graf.end();it++)
        if(!multime(it->x, it->y))
        {
            s+=it->c;
            adaug(it->x, it->y);
            sol.push_back(*it);
        }
    printf("%d\n%d\n", s, sol.size());
    for(it=sol.begin();it!=sol.end();it++)
        printf("%d %d\n", it->x, it->y);
    return 0;
}