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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <tuple<int,int,int>> muchii;
vector <int> v[101];
int n,m,cost,nr,x,y,c,h[101],p[101];
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()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        h[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        f>>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++)
    {
        x=get<1>(muchii[i]);
        y=get<2>(muchii[i]);
        c=get<0>(muchii[i]);
        if(Find(x)!=Find(y))
        {
            nr++;
            cost+=c;
            v[nr].push_back(x);
            v[nr].push_back(y);
            Union(x,y);
        }

    }

    g<<cost<<'\n'<<nr<<'\n';
    for(int i=1;i<=nr;i++)
        g<<v[i][0]<<' '<<v[i][1]<<'\n';

    return 0;
}