#include <bits/stdc++.h>
#define mp make_pair
#define pa pair <int, int>
#define dpa pair <int, pa>
#define NMAX 200001

using namespace std;

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

int n, m, ans;

vector < pa > v[NMAX];
priority_queue < dpa, vector <dpa>, greater <dpa> > q;
bitset <NMAX> b;
vector < pa > sol;

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

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

    b[1] = 1;
    for(int i = 0; i < v[1].size(); i++)
    {
        int nod_urm, cost;
        nod_urm = v[1][i].first;
        cost = v[1][i].second;
        q.push(mp(cost,mp(nod_urm, 1)));

    }

    while(!q.empty())
    {
        int nod, cost, last;
        cost = q.top().first;
        nod = q.top().second.first;
        last = q.top().second.second;
        q.pop();

        if(b[nod] == 1)
            continue;
        b[nod] = 1;
        ans += cost;
        sol.push_back(mp(last, nod));
        for(int i = 0; i < v[nod].size(); i++)
        {
            int nod_urm, cost_urm;
            nod_urm = v[nod][i].first;
            cost_urm = v[nod][i].second;

                q.push(mp(cost_urm, mp(nod_urm, nod)));


        }

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


    return 0;
}