#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 2e5 + 5;
struct muchie{
    int from, to, cost;
    bool operator <(const muchie& a) const
    {
        return cost > a.cost;
    }
};

vector<muchie> G[Nmax];
vector<pair<int,int>> sol;
bool vizitat[Nmax];
int cost_final;

int main()
{
    int N, M;
    in >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        muchie m;
        m.from = x;
        m.to = y;
        m.cost = c;
        G[x].push_back(m);
        m.to = x;
        m.from = y;
        G[y].push_back(m);
    }
    priority_queue<muchie> Q;
    for(auto i : G[1])
        Q.push(i);
    vizitat[1] = 1;

    while(!Q.empty())
    {
        muchie m = Q.top();
        Q.pop();
        if(!vizitat[m.to])
        {
            vizitat[m.to] = 1;
            cost_final += m.cost;
            sol.push_back({m.from,m.to});
            for(auto i : G[m.to])
            {
                Q.push(i);
            }
        }
    }
    out << cost_final << '\n';
    out << sol.size() << '\n';
    for(auto i : sol)
        out << i.first << " " << i.second << '\n';
    return 0;
}