#include <bits/stdc++.h>
#define mp std::make_pair
#define dimn 200005
#define index first
#define cost second
#define adj second
#define ll long long
using data = std::pair<int, std::pair <int, int>>;

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

int N, M;
bool seen[dimn];
std::priority_queue <data> pq;
std::vector <std::pair <int, int>> edge[dimn];
std::vector <std::pair <int, int>> sol;
ll sum;

void prim(int start=1) {
    seen[start] = true;
    for (int i=0; i<edge[start].size(); i++) {
        int son = edge[start][i].index;
        int cost = edge[start][i].cost;
        pq.push(mp(-cost, mp(start, son)));
    }

    int nsol=0; data pres;
    while(nsol < N-1) {
        while(seen[pq.top().adj.second])
            pq.pop();
        nsol++;
        pres = pq.top();
        pq.pop();

        seen[pres.adj.second] = 1;
        sol.push_back(mp(pres.adj.first, pres.adj.second));
        sum += pres.first;

        for (int i=0; i<edge[pres.adj.second].size(); i++)
            if(!seen[edge[pres.adj.second][i].first])
                pq.push(mp(-edge[pres.adj.second][i].second, mp(pres.adj.second, edge[pres.adj.second][i].first)));
    }
}

void citire() {
    f >> N >> M;
    for (int i=0, y, x, c; i<M; i++) {
        f >> x >> y >> c;
        edge[x].push_back(mp(y, c));
        edge[y].push_back(mp(x, c));
    }
}
void rezolvare() {
    prim();
    g << -sum << "\n" << N-1 << "\n";
    for(int i=0; i<sol.size(); i++)
        g << sol[i].first << " " << sol[i].second << "\n";
}

int main()
{
    citire();
    rezolvare();

    return 0;
}