#include <bits/stdc++.h>

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

struct edge
{
    int e1, e2, cost;
};

edge muchii[400005];
vector<edge> rez;
int TT[200005];
int RG[200005];
int n, m, cost;

bool cmp(edge m1, edge m2)
{
    return m1.cost < m2.cost;
}

void Read()
{
    f>>n>>m;
    for(int i = 1;i <= n;++i)
    {
        RG[i] = 1;
        TT[i] = i;
    }
    for(int i = 1;i <= m;++i)
        f>>muchii[i].e1>>muchii[i].e2>>muchii[i].cost;
    sort(muchii + 1, muchii + m + 1, cmp);
}

int find(int x)
{
    int R, y;

    for(R = x;R != TT[R];R = TT[R]);

    while(x != TT[x])
    {
        y = TT[x];
        TT[x] = R;
        x = y;
    }
    return R;
}

void unite(int x,int y)
{
    if(RG[x] > RG[y])
        TT[y] = x;
    else
        TT[x] = y;

    if(RG[x] == RG[y]) ++RG[y];
}

void Solve()
{
    cost = 0;
    for(int i = 1;i <= m;++i)
        if(find(muchii[i].e1) != find(muchii[i].e2))
        {
            unite(find(muchii[i].e1), muchii[i].e2);
            cost += muchii[i].cost;
            rez.push_back({muchii[i].e1, muchii[i].e2, 0});
        }
}

void Print()
{
    g<<cost<<'\n';
    g<<rez.size()<<'\n';
    for(int i = 0;i < rez.size();++i)
        g<<rez[i].e1<<" "<<rez[i].e2<<'\n';
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}