#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
#include <vector>

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

using namespace std;
typedef long long int ll;

struct CEVA{
    int x, y, cost;
};

const int nMax = 4e5 + 5;

int n, k, TOTAL;
int TT[nMax], rg[nMax];

pair<int,int> rez[nMax], m[nMax];
vector<CEVA> muchii;

bool cmp(CEVA x,CEVA y)
{
    return x.cost < y.cost;
}

int reprz(int x)
{
    while(TT[x] != x)x = TT[x];
    return x;
}

void unire(int x,int y)
{
    if (rg[x] < rg[y])TT[x] = y;
    else if (rg[x] > rg[y])TT[y] = x;
    else if (rg[x] == rg[y])TT[x] = y,rg[y]++;
}

void solve()
{
    for (int i = 1;i <= k;i++){
        TT[i] = i;
        rg[i] = 0;
    }
    int nrr = 0;
    sort(muchii.begin(),muchii.end(),cmp);
    for (size_t it = 0;it < muchii.size();it++){
        int x = reprz(muchii[it].x);
        int y = reprz(muchii[it].y);
        if (x != y)unire(x,y),TOTAL += muchii[it].cost,rez[++nrr] = {muchii[it].x,muchii[it].y};
    }
    g << TOTAL << '\n' << nrr << '\n';
    for (int i = 1;i <= nrr;i++)g << rez[i].first << " " << rez[i].second << '\n';
}

int main()
{
    f >> n >> k;
    for (int i = 1;i <= k;i++){
        int x, y, cost;
        f >> x >> y >> cost;
        muchii.push_back({x,y,cost});
    }
    solve();
}