#include <bits/stdc++.h>
using namespace std;

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

struct Muchie{int x, y, c;}X;
struct Corecte{int x, y;}Y;
vector <Muchie> v;
vector <Corecte> V;
vector <int> t;

bool valid(Muchie st, Muchie dr)
{
    return st.c < dr.c;
}

void init(int n)
{
    for(int i=1; i<=n; i++)
        t[i] = -1;
}

int det(int x)
{
    if(t[x] < 0)
        return x;
    else
    {
        t[x] = det(t[x]);
        return t[x];
    }
}

void uneste(int t1, int t2)
{
    if(t[t1] <= t[t2])
    {
        t[t1] += t[t2];
        t[t2] = t1;
    }
    else
    {
        t[t2] += t[t1];
        t[t1] = t2;
    }
}

int main()
{
    int n, m, s=0;
    fin>>n>>m;
    while(m)
    {
        fin>>X.x>>X.y>>X.c;
        v.push_back(X);
        m--;
    }
    t.resize(n+1);
    init(n);
    sort(v.begin(), v.end(), valid);
    for(int i=0; i<v.size(); i++)
    {
        int t1 = det(v[i].x);
        int t2 = det(v[i].y);
        if(t1 != t2)
        {
            Y.x = v[i].x;
            Y.y = v[i].y;
            V.push_back(Y);
            s += v[i].c;
            uneste(t1, t2);
        }
    }
    fout<<s<<"\n"<<n-1<<"\n";
    for(int i=0; i<V.size(); i++)
        fout<<V[i].x<<" "<<V[i].y<<"\n";
    return 0;
}