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

//ifstream f ("heapuri.in");
//ofstream g ("heapuri.out");

int t[NMAX],h[NMAX],cmin,n,m;


struct Muchie{
    int x,y,c;
}muc[NMAX];

vector <Muchie> muchii_folosite;

bool cmp(Muchie a,Muchie b)
{
    return a.c < b.c;
}

int Find(int x)
{
    int r = x;
    while(t[r] != r)r = t[r];
    int i=x,j;
    while(i != r)
    {
        j=t[i];
        t[i] = r;
        i = j;
    }
    return r;
}

void Union(int x,int y)
{
    if(Find(x) == Find(y))return;

    int rx = Find(x), ry = Find(y);

    if(h[rx] < h[ry])t[rx] = ry;
    else
    if(h[ry] < h[rx])t[ry] = rx;
    else
        t[rx] = ry,h[rx]++;
}

void kruskal()
{
    sort(muc+1,muc+1+m,cmp);

    int k = 1,i=1;
    while(k < n)
    {
        while(Find(muc[i].x) == Find(muc[i].y))i++;
        Union(muc[i].x,muc[i].y);
        cmin+=muc[i].c;
        muchii_folosite.push_back(muc[i]);
        k++;
    }

    cout << cmin << '\n';
    cout << muchii_folosite.size() << '\n';
    for(vector<Muchie>::iterator it = muchii_folosite.begin();it!=muchii_folosite.end();++it)
        cout << it->x << ' ' << it->y << '\n';
}

void citire()
{
    cin >> n >> m;

    for(int i=1;i<=n;++i)t[i] = i,h[i] = 1;

    for(int i=1;i<=m;++i)
        cin >> muc[i].x >> muc[i].y >> muc[i].c;
}

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

    citire();
    kruskal();
    return 0;
}