/*
                         __
                   _.--""  |
    .----.     _.-'   |/\| |.--.
    |    |__.-'   _________|  |_)  _______________
    |  .-""-.""""" ___,    `----'"))   __   .-""-.""""--._
    '-' ,--. `    |Cezar| .---.       |:.| ' ,--. `      _`.
     ( (    ) ) __|  7  |__\\|// _..-- \/ ( (    ) )--._".-.
      . `--' ;\__________________..--------. `--' ;--------'
       `-..-'                               `-..-'
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

struct muchie{
    int y,cost;
};

const int N = 2e5;
const int INF = (1<<30);

vector <muchie> v[N];
int tata[N];
int dp[N];
bitset<N>inq, in_t;

struct comparare{
    bool operator()(muchie a, muchie b){
        return a.cost>b.cost;
    }
};

void init(int n){
    for(int i=0;i<n;i++){
        dp[i] = INF;
    }
}

int prim(){
    int rez = 0;
    priority_queue<muchie,vector<muchie>,comparare>q;
    muchie x;
    dp[1] = 0;
    x.y = 1;
    x.cost = 0;
    q.push(x);
    while(!q.empty()){
        x = q.top();
        q.pop();
        if(in_t[x.y])
            continue;
        //cout<<dp[x.y]<<' '<<x.y<<'\n';
        rez += dp[x.y];
        in_t[x.y] = true;
        for(auto y: v[x.y]){
            if(!in_t[y.y] && dp[y.y] > y.cost){
                //cout<<y.y<<' '<<x.y<<'\n';                dp[y.y] = y.cost;
                dp[y.y] = y.cost;
                tata[y.y] = x.y;
                q.push(y);
            }
        }
    }
    return rez;
}

int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n,m,x,y,cost;
    in>>n>>m;
    muchie add;
    while(m--){
        in>>x>>y>>cost;
        add.y = y;
        add.cost = cost;
        v[x].push_back(add);
        add.y = x;
        v[y].push_back(add);
    }
    init(n+1);
    out<<prim()<<'\n';
    out<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        out<<tata[i]<<' '<<i<<'\n';
    return 0;
}