#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct muchie{
    int x, y;
    int cost;
    bool operator < (const muchie &other) const{
        return cost>other.cost;
    }
};

struct nod{
    int num, parinte, siz;
};

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

vector<nod> v;
vector<pair<int, int>> sol;
int summax;

int root(int i) {
    if (v[i].parinte == 0)
        return i;
    return v[i].parinte = root(v[i].parinte);
}

bool joined(int x, int y)
{
    return root(x)==root(y);
}

void join(int x, int y)
{
    int rx=root(x), ry=root(y);
    if(v[rx].siz>v[ry].siz)
        swap(rx, ry);
    v[rx].parinte=ry;
    v[ry].siz+=v[rx].siz;
}

void add_to_sol(muchie t)
{
    sol.push_back({t.x, t.y});
    summax+=t.cost;
}

void print_sol()
{
    fout << summax << '\n';
    fout << sol.size() << '\n';
    for(auto t: sol)
        fout << t.first << ' ' << t.second << '\n';
}

int main()
{
    int n, m;
    priority_queue<muchie> pq;
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        pq.push({a, b, c});
    }
    for(int i=1; i<=n; i++)
        v.push_back({i,0,1});
    for(int i=1; i<=m; i++)
    {
        muchie t=pq.top();
        pq.pop();
        if(!joined(t.x, t.y))
        {
            join(t.x, t.y);
            add_to_sol(t);
        }
    }
    print_sol();
    return 0;
}