// APM prim cu min-heap
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
#include <bitset>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
const int Nmax = 200022;

char used[Nmax];
vector<pii> G[Nmax];

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

    int N, M, a, b, d;
    f >> N >> M;

    while(M--)
    {
        f >> a >> b >> d;
        G[a].push_back(make_pair(b, d));
        G[b].push_back(make_pair(a, d));
    }
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> Q;
    used[1] = 1;
    for(auto vecin: G[1])
        Q.push(make_pair(vecin.second, make_pair(1, vecin.first)));

    int cost = 0;
    vector<pii> solution;

    while(!Q.empty())
    {
        pair<int, pii> P = Q.top(); Q.pop();
        if (!used[P.second.second])
        {
            int varf = P.second.second;
            cost += P.first;
            used[varf] = 1;
            solution.push_back(P.second);
            for (auto vecin: G[varf])
                if (!used[vecin.first])
                    Q.push(make_pair(vecin.second, make_pair(varf, vecin.first)));
        }
    }
    g << cost << '\n';
    g << solution.size() << '\n';
    for (auto x: solution)
        g << x.first << ' ' << x.second << '\n';

    return 0;
}