#include <bits/stdc++.h>
#define iPair pair<int, int>

using namespace std;

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

int n, m;
vector<pair<int, iPair>> G, ans;
int t[200001], rang[200001];
int costmin;

void Citire()
{
    int i, j, p;
    fin >> n >> m;
    for(int c=0; c<m; c++)
    {
        fin >> i >> j >> p;
        G.push_back(pair<int, iPair>(p, iPair(i, j)));
    }
}

int Radacina(int k)
{
    if(t[k]==0)
        return k;
    int x=Radacina(t[k]);
    t[k]=x;
    return x;
}

void Kruskal()
{
    int i, cnt=0, x, y, cost;
    sort(G.begin(), G.end());
    for(i=0; cnt!=n-1; i++)
    {
        cost=G[i].first;
        x=G[i].second.first;
        y=G[i].second.second;
        int rx=Radacina(x), ry=Radacina(y);
        if(rx==ry)
            continue;
        else
        {
            cnt++;
            costmin+=cost;
            ans.push_back(G[i]);
            if(rang[rx]<rang[ry])
                t[rx]=ry;
            else
            {
                t[ry]=rx;
                if(rang[rx]==rang[ry])
                    rang[rx]++;
            }
        }
    }
}

void Afisare()
{
    int i;
    fout << costmin << '\n' << n-1 << '\n';
    for(i=0; i<ans.size(); i++)
        fout << ans[i].second.first << ' ' << ans[i].second.second << '\n';
}

int main()
{
    Citire();
    Kruskal();
    Afisare();
    return 0;
}