#include <bits/stdc++.h>
#define mama pair <int, pair <int, int> >
#define mp make_pair

using namespace std;

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

vector <mama> G[200005];
priority_queue < mama, vector<mama>, greater<mama> > H;
vector <pair <int, int> > sol;

long long cost;

int n, m, x, y, c;

bool viz[200005];

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

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

    for (int i = 0; i < G[1].size(); i++)
    {
        H.push(G[1][i]);
    }

    viz[1] = true;

    for (int i = 1; i < n; i++)
    {
        while (viz[H.top().second.second])
        {
            H.pop();
        }

        mama t = H.top();
        sol.push_back(mp(t.second.first, t.second.second));
        viz[t.second.second] = true;
        cost = cost + t.first;

        for (int j = 0; j < G[t.second.second].size(); j++)
        {
            if (!viz[G[t.second.second][j].second.second])
            {
                H.push(G[t.second.second][j]);
            }
        }
    }

    g << cost << '\n';
    g << sol.size() << '\n';

    for (int i = 0; i < sol.size(); i++)
    {
        g << sol[i].first << " " << sol[i].second << '\n';
    }
    return 0;
}