#include <fstream>
#include <vector>
#include <set>

#define infile "apm.in"
#define outfile "apm.out"

using namespace std;

ifstream in(infile);
ofstream out(outfile);

struct edge{
    int nod;
    int cost;
};

struct compare{
    bool operator()(edge x, edge y){
        return x.cost < y.cost;
    }
};

int n, m;
vector<edge> graph[200005];
int x, y, c;
bool vis[200005];
int parent[200005];
//int costuri[200005];
int costApm;
vector< pair<int, int> > muchi;

int apm(int start)
{
    vis[start] = true;
    multiset<edge, compare> q;
    for(q.insert({start, 0}); muchi.size() < n-1; ){
        edge x = *q.begin();
        q.erase(q.begin());
        if(!vis[x.nod]){
            costApm += x.cost;
            vis[x.nod] = true;
            muchi.push_back(make_pair(parent[x.nod], x.nod));
        }
        for(int j=0; j<graph[x.nod].size(); j++){
            edge nod = graph[x.nod][j];
            if(!vis[nod.nod]){
                q.insert(nod);
                parent[nod.nod] = x.nod;
            }
        }
    }
}

int main()
{
    in >> n >> m;

    for(int i=1; i<=m; i++){
        in >> x >> y >> c;
        graph[x].push_back({y, c});
        graph[y].push_back({x, c});
    }

    apm(1);
    out << costApm << '\n';
    out << muchi.size() << '\n';
    for(int i=0; i<muchi.size(); i++){
        out << muchi[i].first << ' ' << muchi[i].second << '\n';
    }

    return 0;
}