#include <iostream>
#include <vector>
#define maxm 400005
#include <cstdio>
#include <queue>

using namespace std;

int s,n,m,viz[200005],nr;
priority_queue < pair <int , pair <int ,int > > > G;
vector < pair <int ,int  > > q ;

void read()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for (int i=1; i<=m; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        G.push(make_pair(-c,make_pair(x,y)));
    }
    for (int i=1; i<=n; ++i)
        viz[i]=i;
}

void rezolv()
{
    while(!G.empty())
    {
        if (nr==n-1)
            break;
        int x=G.top().second.first;
        int y=G.top().second.second;
        int c=-G.top().first;
        G.pop();
        if (viz[x]!=viz[y])
        {
            nr++;
            int d=viz[y];
            for (int i=1; i<=n; ++i)
                if (d==viz[i])
                    viz[i]=viz[x];
            q.push_back(make_pair(x,y));
            s+=c;
        }

    }
    printf("%d\n%d\n",s,nr);
    for (vector <pair <int ,int > > :: iterator it=q.begin() ; it!=q.end(); ++it)
        printf("%d %d\n", it->second,it->first);
}

int main()
{

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    rezolv();
    return 0;
}