#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

#define Inf (1<<31)-1
#define NMax 200001

using namespace std;

class tri {
public:
    int x, y, cost;
    bool operator() (tri a,tri b)
    {
        return a.cost>b.cost;
    }
};

inline tri make_tri(int _x,int _y,int _cost)
{
    tri t;
    t.x=_x;
    t.y=_y;
    t.cost=_cost;
    return t;
}

vector<pair<int, int> > v[NMax], apme;
bool viz[NMax];
priority_queue<tri, vector<tri>, tri> q;
int n, m, x, y, z, cost;

int main()
{
    ifstream fin ("apm.in");
    ofstream fout ("apm.out");
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> x >> y >> z,
        v[x].push_back (make_pair (y, z)),
        v[y].push_back (make_pair (x, z));

    for (int i = 1; i <= n; i++)
        viz[i] = 0;

    viz[1] = 1;
    for (int i = 0; i < v[1].size (); i++)
        q.push ( make_tri (1, v[1][i].first,v[1][i].second) );

    for (int i = 1; i < n; i++) {
        while (!q.empty () && viz[q.top().y])
            q.pop ();
        tri e = q.top ();

        cost += e.cost;
        viz[e.y] = 1;
        apme.push_back (make_pair (e.x, e.y));
        q.pop ();

        for (vector<pair<int, int> >::iterator i = v[e.y].begin (); i != v[e.y].end (); i++)
            if (!viz[i->first])
                q.push (make_tri ( e.y, i->first, i->second) );
    }

    fout << cost << '\n' << apme.size () << '\n';
    for (int i = 0; i < apme.size (); i++)
        fout << apme[i].first << ' ' << apme[i].second << '\n';
    return 0;
}