#include <bits/stdc++.h>
#define NMAX 5005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
struct edge
{
    int x, y, cost;
};
edge v[NMAX];
int viz[NMAX];
int t[105];
int s;
int counter;

bool comp(edge a, edge b)
{
    return a.cost<b.cost;
}
void read();
int main()
{
    read();
    sort(v+1, v+m+1, comp);
    for(int i=1; i<=n; ++i)
        t[i]=i;

    for(int i=1; i<=m; ++i)
    {
        if(t[v[i].x]==t[v[i].y])
            continue;
        viz[i]=1;
        s+=v[i].cost;
        int ax=t[v[i].x];
        int ay=t[v[i].y];
        for(int j=1; j<=n; ++j)
            if(t[j]==ay)
            {
                t[j]=ax;
            }
    }

    fout<<s<<'\n';
    fout<<n-1<<'\n';
    for(int i=1; i<=m; ++i)
    {
        if(viz[i])
        {
            fout<<v[i].x<<' '<<v[i].y<<'\n';
        }
    }
    return 0;
}
void read()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
}