#include <bits/stdc++.h>

using namespace std;

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

int n,m,s;
bool viz[200005];
vector<pair<int,int>>a[200005],sol;
priority_queue<pair<int,pair<int,int>>>h;

void citire()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y,z;
        in >> x >> y >> z;
        a[x].push_back(make_pair(z,y));
        a[y].push_back(make_pair(z,x));
    }
}


void prim()
{
    viz[1] = true;
    for (int i = 0; i < a[1].size(); i++)
    {
        int vecin2,cost2;
        vecin2 = a[1][i].second;
        cost2 = -a[1][i].first;
        if (viz[vecin2] == false)
            h.push(make_pair(cost2,make_pair(1,vecin2)));
    }
    while (!h.empty())
    {
        int nod,vecin,cost;
        nod = h.top().second.first;
        vecin = h.top().second.second;
        cost = h.top().first;
        h.pop();
        if (viz[vecin] == true)
            continue;
        viz[vecin] = true;
        sol.push_back(make_pair(nod,vecin));
        s += -cost;
        for (int i = 0; i < a[vecin].size(); i++)
        {
            int vecin2,cost2;
            vecin2 = a[vecin][i].second;
            cost2 = -a[vecin][i].first;
            if (viz[vecin2] == false)
                h.push(make_pair(cost2,make_pair(vecin,vecin2)));
        }
    }
}

void afisare()
{
    out << s << '\n' << sol.size() << '\n';
    for (int i = 0; i < sol.size(); i++)
        out << sol[i].first << " " << sol[i].second << '\n';
}

int main()
{
    citire();
    prim();
    afisare();
    return 0;
}