#include <bits/stdc++.h>

using namespace std;

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

priority_queue< pair< int, pair<int, int > > > coada;
vector<pair<int, int>> graf[200001];
int n,m, v[200001], cost;

int main()
{
    fin >> n >> m;
    int x, y, c;
    while(m)
    {
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
        m--;
    }

    vector<pair<int, int>> ans;
    for(auto x: graf[1]) coada.push({-x.second, {1, x.first}});

    v[1] = 1;

    while(!coada.empty())
    {
        x = coada.top().second.first;
        y = coada.top().second.second;
        c = -coada.top().first;
        coada.pop();
        if(v[y]) continue;
        v[y] = 1;
        ans.push_back({x, y});
        cost += c;

        for(auto next: graf[y])
        {
            if(!v[next.first])
                coada.push({-next.second, {y, next.first}});

        }
    }
    fout << cost << '\n' << ans.size() << '\n';

    for(auto p: ans)
        fout << p.first << ' ' << p.second << '\n';
}