#include <bits/stdc++.h>
using namespace std;
//ifstream fin("apm.in");
//ofstream fout("apm.out");
const int maxn=2e5+4;
bool visited[maxn];

struct str{
    int nod, cost;
    bool operator <  (const str & aux) const{
        return cost > aux.cost;
    }
    int ant;
};
int main()
{
    int n, m;
    cin>>n>>m;
    vector<vector<pair<int, int>>> mc(n+1);
    while(m--){
        int x, y, c;
        cin>>x>>y>>c;
        mc[x].push_back({y, c});
        mc[y].push_back({x, c});
    }
    priority_queue<str> pq;
    int cost=0, nr=-1;
    pq.push({1, 0, -1});
    vector<pair<int, int>> out;
    while(!pq.empty()){
        int nod=pq.top().nod, c=pq.top().cost, ant=pq.top().ant;
        pq.pop();
        if(visited[nod]) continue;
        visited[nod]=1;
        nr++;
        cost+=c;
        if(ant!=-1){
            out.push_back({ant, nod});
        }
        for(int i=0; i<mc[nod].size(); i++){
            int nou=mc[nod][i].first, cn=mc[nod][i].second;
            if(!visited[nou])pq.push({nou, cn, nod});
        }
    }
    cout<<cost<<"\n"<<nr<<"\n";
    for(int i=0; i<nr; i++){
        cout<<out[i].first<<" "<<out[i].second<<"\n";
    }
    return 0;
}