#include <bits/stdc++.h>

using namespace std;

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

int father[100005],depth[100005], n, m, a, b, tip;
struct d{
    int from, to, cost;
}muchii[400005];

int cost;

vector<pair<int,int> >rez;

class cmp{
public:
    bool operator()(d a, d b)
    {
        return a.cost<b.cost;
    }
};

int old_man(int ind)
{
    if (father[ind]==ind)
        return ind;
    return old_man(father[ind]);
}

void solve()
{
    int nod1, nod2, aux1, aux2;
    for (int i=1; i<=m; ++i)
    {
        nod1=muchii[i].from;
        nod2=muchii[i].to;
        aux1=old_man(nod1);
        aux2=old_man(nod2);
        if (aux1!=aux2)
        {
            if (depth[aux1]<depth[aux2])
                father[aux1]=aux2;
            else if (depth[aux2]<depth[aux1])
                father[aux2]=aux1;
            else
                father[aux1]=aux2,depth[aux2]++;
            cost+=muchii[i].cost;
            rez.push_back({nod1,nod2});
        }
    }
    g << cost << '\n';
    g << n-1 << '\n';
    for (auto &v:rez)
        g << v.first <<' ' << v.second << '\n';
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=n; ++i)
        father[i]=i, depth[i]=1;
    for (int i=1; i<=m; ++i)
        f >> muchii[i].from >> muchii[i].to >> muchii[i].cost;
    sort(muchii+1,muchii+m+1,cmp());
    solve();
    return 0;
}