#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> adj;
vector <pair <int, int> > rez;
map <pair<int, int>, int> mp;
priority_queue < tuple <int, int, int> > pq;

int viz[200005], mn = 210000000, sum=0;

void prim(int nod)
{
    for(auto i:adj[nod])
    {
        if(viz[i]==0)
            pq.push(make_tuple((-1)*mp[{nod, i}], i, nod));
    }
    while(!pq.empty() && viz[get<1>(pq.top())]==1){
        pq.pop();
    }
    if(pq.empty())
        return;
    viz[get<1>(pq.top())] = 1;
    sum += get<0>(pq.top())*(-1);
    rez.push_back({get<2>(pq.top()), get<1>(pq.top())});
    nod=get<1>(pq.top());
    pq.pop();
    prim(nod);
}

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    int n, m, x, y, val;
    cin >> n >> m;
    adj.resize(n + 5);
    for(int i = 0; i < m; i++){
        cin >> x >> y >> val;
        mp[{x, y}] = mp[{y, x}] = val;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    viz[1] = 1;
    prim(1);
    cout<<sum<<'\n' << rez.size() << "\n";
    for(int i = 0; i < rez.size(); i++){
        cout << rez[i].first << " " << rez[i].second << "\n";
    }
    return 0;
}