#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 200000;
int tata[NMAX+5];
int g[NMAX+5];
struct muchie
{
    int x, y, cost;
}v[NMAX+5];
void define(int n)
{
    for(int i = 1; i<= n; i++)
    {
        tata[i] = i;
        g[i] = 1;
    }
}
int Find(int nod)
{
    while(nod != tata[nod])
        nod = tata[nod];
    return nod;
}
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if(g[a]>g[b])
        swap(a,b);
    tata[a] = b;
    g[b]+=g[a];
}
bool cmp(muchie a, muchie b)
{
    if(a.cost < b.cost)
        return 1;
    else
        return 0;
}
vector <pair <int,int> > r;
int main()
{
    int n, m, l;
    long long c = 0;
    fin >> n >> m;
    define(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(int i = 1; i<=m; i++)
    {
        if(Find(v[i].x)!=Find(v[i].y))
        {
            Union(v[i].x,v[i].y);
            c+=v[i].cost;
            l = Find(v[i].x);
            r.push_back(make_pair(v[i].x,v[i].y));
            if(g[l]==n)
            {
                fout<<c<<"\n";
                fout<<n-1<<"\n";
                for(int j = 0; j < n-1; j++)
                {
                    fout<<r[j].first<<" "<<r[j].second<<"\n";
                }
            }
        }
    }
    return 0;
}