#include <iostream>
#include <vector>
#define maxm 400005
#include <cstdio>
#include <algorithm>
using namespace std;

int s,n,m,viz[200005],nr;
vector < 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_back(make_pair(c,make_pair(x,y)));
    }
    sort(G.begin(),G.end());
    for (int i=1;i<=n;++i)
        viz[i]=i;
}

void rezolv()
{
   for (vector < pair <int , pair <int ,int > > > :: iterator it=G.begin() ; it!=G.end() ; ++it)
            {
                if (nr==n-1)
                    break;
                if (viz[it->second.first]!=viz[it->second.second])
                {
                    nr++;
                    int d=viz[it->second.second];
                    for (int i=1;i<=n;++i)
                        if (d==viz[i])
                            viz[i]=viz[it->second.first];
                    q.push_back(make_pair(it->second.first,it->second.second));
                    s+=it->first;
                }
            }
    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;
}