#include <iostream>
#include<fstream>
#include<tuple>
#include<algorithm>
#include<vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

vector <tuple<int,int,int>> muchii;
vector<int> v[200001];

int n,m,cost,nr,x,y,c,p[200001],h[200001];

int Find(int x)
{
    while(x!=p[x])
        x=p[x];
    return x;
}

void Union(int x,int y)
{
    x=Find(x);
    y=Find(y);
    if(x!=y)
    {
        if(h[x]<h[y])
            p[x]=y;
        else if (h[y]<h[x])
                p[y]=x;
        else
            {
                p[x]=y;
                h[y]++;
            }
    }
}
int main()
{

    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        h[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        muchii.push_back(make_tuple(c,x,y));
    }
    sort(muchii.begin(),muchii.end());
    cost=0;
    nr=0;
    for(int i=0;i<m;i++)
    {
        c=get<0>(muchii[i]);
        x=get<1>(muchii[i]);
        y=get<2>(muchii[i]);
        if(Find(x)!=Find(y))
        {
            nr++;
            cost+=c;
            v[nr].push_back(x);
            v[nr].push_back(y);
            Union(x,y);
        }
    }
    fout<<cost<<endl;
    fout<<nr<<endl;
    for(int i=1;i<=nr;i++)
        fout<<v[i][0]<<" "<<v[i][1]<<endl;
    return 0;
}