#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,t[101],h[101];
vector<tuple<int,int,int> > v;
vector<pair<int,int> > vsol;

int comp(tuple<int,int,int> x, tuple<int,int,int> y)
{
    return get<0>(x)<get<0>(y);
}

int find_compression(int x)
{
    int r=x,aux;
    while(t[r]!=r)
        r=t[r];
    while(t[x]!=r)
    {
        aux=t[x];
        t[x]=r;
        x=aux;
    }
    return r;
}

int union_pondered(int x, int y)
{
    if(x==y)
        return 0;
    if(h[x]<h[y])
        t[x]=y;
    else
    {
        t[y]=x;
        if(h[x]==h[y])
            h[x]++;
    }
    return 1;
}

int main()
{
    int x,y,c,r1,r2,sol=0;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v.push_back(make_tuple(c,x,y));
    }
    sort(v.begin(),v.end(),comp);
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    for(auto it : v)
    {
        c=get<0>(it);
        x=get<1>(it);
        y=get<2>(it);

        r1=find_compression(x);
        r2=find_compression(y);
        if(union_pondered(r1,r2))
        {
            sol+=c;
            vsol.push_back({x,y});
        }
    }
    fout<<sol<<'\n';
    fout<<n-1<<'\n';
    for(auto it : vsol)
    {
        fout<<it.first<<" "<<it.second<<'\n';
    }
}