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

using namespace std;

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

struct muchie
{
    int cost, dir, home;

    bool operator<(const muchie &y) const { return cost > y.cost; }

    bool operator>(const muchie &y) const { return cost < y.cost; }
};

#define MAX_N 200001

vector <muchie> graf[MAX_N];

bool viz[MAX_N];

priority_queue<muchie> Q;

struct ptAns
{
    int a, b;
};
vector <ptAns> v;

int main()
{
    int n, m, x, y, c, ans = 0;
    in >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        in >> x >> y >> c;
        graf[x].push_back({c, y, x});
        graf[y].push_back({c, x, y});
    }

    viz[1] = 1;
    for(auto x : graf[1])
    {
        Q.push(x);
    }

    for(int i = 1; i < n; ++i) //la fiecare pas luam cate o muchie noua
    {
        muchie it = Q.top();
        Q.pop();

        while(viz[it.dir])
        {
            it = Q.top();
            Q.pop();
        }

        //acum putem folosi muchia
        v.push_back({it.dir, it.home});
        viz[it.dir] = 1;
        for(auto x : graf[it.dir])
        {
            if(!viz[x.dir])
                Q.push(x);
        }
        ans += it.cost;
    }

    out << ans << '\n' << v.size() << '\n';
    for(auto x : v)
    {
        out << x.a << " " << x.b << '\n';
    }
    return 0;
}