#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200010;
vector<pair<int,int> > V[MAXN];

vector<pair<int,int> > rs;
int N, M;
long long SUM = 0;
bool inMST[MAXN] = {false};
int PAR[MAXN];
int KEY[MAXN];

void prim(int start) {
    for (int i = 1; i <= N;i++) {
        PAR[i] = -1;
        KEY[i] = INT_MAX;
        inMST[i] = false;
    }    

    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q;

    Q.push({0, start});
    KEY[start] = 0;
    while (!Q.empty()) {
        int curr = Q.top().second;
        Q.pop();
        inMST[curr] = true; 
        for (auto edge: V[curr]) {
            int nextNode = edge.first;
            int dist = edge.second;
            if (!inMST[nextNode] && dist < KEY[nextNode]) {
                KEY[nextNode] = dist;
                Q.push({KEY[nextNode], nextNode});
                PAR[nextNode] = curr;
            }
        }

    }


}

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

    fin >> N >> M;
    for (int from, to ,dist; M--;) {
        fin >> from >> to >> dist;
        V[from].push_back({to,dist});
        V[to].push_back({from, dist});
    }

    prim(1);
    for (int i = 1; i <= N;i++) SUM += KEY[i];
    cout << SUM << endl;
    cout << N - 1 << endl;
    
    for (int i = 2; i <= N; i++) cout << i << " " << PAR[i] <<endl;
    
    


    return 0;
}