#include <fstream>
#include <climits>
#include <queue>

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

int const nmax = 200000;
int const INF = INT_MAX;
int dist[nmax + 5];
struct edge {
    int target, w;
};
std::vector <std::vector <edge> > adj;
std::vector <edge> ans;
struct pqelem {
    int val, source, target;
    bool operator < (pqelem const other) const {
        return val > other.val;
    }
};
std::priority_queue <pqelem> pq;

int main()
{
    int n, m;
    fin >> n >> m;
    adj.resize (n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        fin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    int cost = 0;
    pq.push({0, 1, 1});
    dist[1] = 0;
   for (int k = 1; k <= n; ) {
        pqelem top = pq.top();
        pq.pop();
        if (dist[top.target] == -INF)
            continue;
        k++;
        cost += top.val;
        dist[top.target] = -INF;
        ans.push_back({top.target, top.source});
        int lim = adj[top.target].size();
        for (int i = 0; i < lim; i++) {
            if (adj[top.target][i].w < dist[adj[top.target][i].target]) {
                dist[adj[top.target][i].target] = adj[top.target][i].w;
                pq.push({adj[top.target][i].w, top.target, adj[top.target][i].target});
            }
        }
    }
    fout << cost << "\n";
    int lim = ans.size();
    fout << lim - 1 << "\n";
    for (int i = 1; i < lim; i++) {
        fout << ans[i].target << " " << ans[i].w << "\n";
    }
    return 0;
}