#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,x,y,pret,i,cost,parinte[200001],Rank[200001];
vector <tuple<int,int,int>> v;
vector <pair<int,int>> muchii_afis;

int cauta(int x)
{
    if(parinte[x] != x)
        parinte[x] = cauta(parinte[x]);
    return parinte[x];
}
void Union(int x,int y)
{
    if(Rank[x] > Rank[y])
    {
        parinte[y] = x;
        Rank[x] += Rank[y];
    }
    else
    {
        parinte[x] = y;
        Rank[y] += Rank[x] + 1;
    }
}
bool cmp(tuple <int,int,int> a, tuple <int,int,int> b)
{

    return get<2>(a) < get<2>(b);
}
int main()
{
    ios::sync_with_stdio(0);
    f >> n >> m;
    for(i = 0 ; i < m; ++ i)
    {
        f >> x >> y >> pret;
        v.push_back(make_tuple(x,y,pret));
    }
    for(i = 1; i <= n; ++ i)
        parinte[i] = i;
    sort(v.begin(),v.end(),cmp);
    i = 0;
    while(muchii_afis.size() < n - 1)
    {
        x = cauta(get<0>(v[i]));
        y = cauta(get<1>(v[i]));
        if(x != y)
        {
            cost += get<2>(v[i]);
            muchii_afis.push_back({get<0>(v[i]),get<1>(v[i])});
            Union(x,y);
        }
        ++ i;
    }
    g << cost << '\n' << n - 1 << '\n';
    for(i = 0; i < muchii_afis.size(); ++ i)
        g << muchii_afis[i].first << ' ' << muchii_afis[i].second << '\n';
}