#include <bits/stdc++.h>
using namespace std;

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

struct muchie{
    int x, y, cost;
    bool friend operator < (muchie a, muchie b){
        return a.cost >b.cost;}
}a;
int n, m, x, y, c, fx, fy, cost_min;
priority_queue<muchie> pq;
vector<pair<int, int> >v;
int tata[200005];
int h[200005];

int Find(int nod)
{
    int x = nod, tmp;
    while(tata[nod]!=0)
        nod = tata[nod];
    while(tata[x]!=0)
    {
        tmp = tata[x];
        tata[x] = nod;
        x = tmp;
    }
    h[nod] = 1;
    return nod;
}

void Union(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if(h[fx]>h[fy])
        tata[fy]=fx;
    else if(h[fy]>h[fx])
        tata[fx] = fy;
    else
    {
        tata[fx] = fy;
        h[fy]++;
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>a.x>>a.y>>a.cost;
        pq.push(a);
    }
    while(!pq.empty())
    {
        x = pq.top().x; y = pq.top().y; c = pq.top().cost; pq.pop();
        fx = Find(x); fy = Find(y);
        if(fx!=fy)
        {
            Union(fx, fy);
            v.push_back(make_pair(x, y));
            cost_min+=c;
        }
    }
    fout<<cost_min<<'\n'<<v.size()<<'\n';
    for(auto i:v)
        fout<<i.first<<' '<<i.second<<'\n';
    return 0;
}