#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
const int NMAX = 200000;
const int MMAX = 400000;
const int INF = 21e8;

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

struct muchii{
    int nod, cost;
};
vector <vector <muchii>> v;
vector <pair <int, int>> ans;
int dist[NMAX + 2]; ///dist[i] = distmin dintre i si componenta formata pana acm
int care[NMAX + 2]; ///care[i] = pt dist[i], care e nodul cu care formeaza
bool viz[NMAX + 2];
int main() {
    int n, m;
    cin >> n >> m;
    v.resize(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        v[a].push_back({b, cost});
        v[b].push_back({a, cost});
    }
    int sum = 0;
    for(int i = 1; i <= n; i++) ///init pt nodul 1
        dist[i] = INF;
    for(auto x : v[1]) {
        dist[x.nod] = x.cost;
        care[x.nod] = 1;
    }
    viz[1] = 1;
    for(int z = 1; z < n; z++) { ///cautam n - 1 muchii
        int nou = 0, maxx = INF;
        for(int i = 1; i <= n; i++) {
            if(!viz[i] && dist[i] < maxx) {
                maxx = dist[i];
                nou = i;
            }
        }
        sum += dist[nou];
        ans.push_back({nou, care[nou]});
        viz[nou] = 1; ///updatam distantele de la nou
        for(auto x : v[nou]) {
            if(!viz[x.nod] && x.cost < dist[x.nod]) {
                dist[x.nod] = x.cost;
                care[x.nod] = nou;
            }
        }
    }
    cout << sum << '\n';
    cout << ans.size() << '\n';
    for(const pair <int, int>& x : ans)
        cout << x.first << " " << x.second << '\n';
    return 0;
}