#include <bits/stdc++.h>
#define N 100005
using namespace std;

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

vector<pair<int, int>> apm;
vector<pair<int, int>> g[N];
int viz[N], d[N], t[N];
int n, m;
int costtotal;

void Prim(){
       priority_queue<pair<int, int>> pq;
        pq.push({0, 1});
        while(!pq.empty()){
            int nod = pq.top().second;
            int cost = -pq.top().first;
            pq.pop();
            if(viz[nod]) continue;
            viz[nod] = 1;
            costtotal += cost;
            if(t[nod] != 0) apm.push_back({t[nod], nod});
            for(auto it : g[nod]){
                if(!viz[it.first]){
                    pq.push({-it.second, it.first});
                    d[it.first] = it.second;
                    t[it.first] = nod;
                }
            }
        }
}

int main()
{
       fin >> n >> m;
         for(int i = 1; i <= m; i++){
              int x, y, c;
              fin >> x >> y >> c;
              g[x].push_back({y, c});
              g[y].push_back({x, c});
         }

            for(int i = 1; i <= n; i++)
                d[i] = 1e9;
            Prim();
            fout << costtotal << '\n';
            fout << n - 1 << '\n';
            for(int i = 2; i <= n; i++)
                fout << i << ' ' << t[i] << '\n';
    return 0;
}