#include <iostream>
#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
using namespace std;

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

struct Muchie{
    int vecin, cost;

    bool operator<(const Muchie& obj) const{
        return this->cost>obj.cost; //> pr min-heap
    }
};

vector<vector<Muchie>> generare_liste_adiacenta_cost(int varfuri, int muchii){
    vector<vector<Muchie>> lista(varfuri);
    int x,y,cost;
    for(int i=0; i<muchii; i++){
        fin>>x>>y>>cost;
        lista[x-1].push_back({y,cost});
        lista[y-1].push_back({x,cost});
    }
    return lista;
}

void Prim(int n, int m, int s, vector<vector<Muchie>>& lista_adiacenta_cu_cost,
            vector<pair<int,int>>& muchii_apcm, long long& cost){

    priority_queue<Muchie> minHeap; //va folosi comparatia definita in struct;
    vector<int> d(n+1, INT_MAX);
    vector<int> tata(n+1, -1);
    vector<bool> inHeap(n+1, true);

    d[s]=0;
    minHeap.push({s,d[s]});
    
    while(!minHeap.empty()){
        int u = minHeap.top().vecin;
        minHeap.pop();
        inHeap[u]=false;

        for(const auto& muchie: lista_adiacenta_cu_cost[u-1]){
            int v = muchie.vecin;
            int cost_muchie=muchie.cost;

            if(inHeap[v] && cost_muchie<d[v]){
                d[v]=cost_muchie;
                tata[v]=u;
                minHeap.push({v,d[v]});
            }
        }
    }

    for(int i=1; i<=n; i++)
        if(i!=s)
            muchii_apcm.push_back({i,tata[i]}), cost+=d[i];

}

int main()
{
    int n,m;
    fin>>n>>m;
    vector<vector<Muchie>> liste_adiacenta_cu_cost = generare_liste_adiacenta_cost(n,m);
    fin.close();

    vector<pair<int, int>> muchii_apcm;
    long long cost = 0;

    Prim(n,m,1,liste_adiacenta_cu_cost,muchii_apcm,cost);

    fout<<cost<<'\n'<<n-1<<'\n';
    for(const auto& muchie : muchii_apcm)
        fout<<muchie.first<<" "<<muchie.second<<'\n';
    fout.close();
    return 0;
}