#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

#define nmax 200010

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

vector <pair<int,int>> la[nmax];
int viz[nmax]={0};
priority_queue <pair<int,int>> pq;
vector <pair<int,int>> apm;


int main()
{   int n,m,x,y,c,s=0,nrmuchii=0;
    f>>n>>m;

    // Se introduc perechile (nod, cost) in liste de adiacenta
    for(int i=1; i<=m; i++){
        f>>x>>y>>c;
        la[x].push_back(make_pair(y,c));
        la[y].push_back(make_pair(x,c));
    }

    // Am creat o structura care tine nodurile unei muchii si costul ei
     struct muchie {
        int x,y,c;
        muchie(int x, int y, int c): x(x), y(y), c(c) {}
    };

    // Am defenit o functie care compara costurile a doua muchii
    struct CompareC {
    bool operator()(muchie const& m1, muchie const& m2)
    {
        return m1.c > m2.c;
    }
    };

    priority_queue<muchie, vector<muchie>, CompareC> pq;
    int v=1;
    viz[1]=1;
    // Introduc in pq muchiile care pornesc din nodul 1
    for(int j=0; j<la[v].size(); j++){
        pq.push(muchie(v,la[v][j].first, la[v][j].second));
    }

    // Cat timp coada nu este goala verific daca mai pot adauga muchii la apm
    while(!pq.empty()){
        // Se extrage muchia cu costul minim
        muchie top = pq.top();
        pq.pop();
        // Daca nodul in care ajunge muchia nu a fost inca vizitat, se adauga la apm
        if(viz[top.y]==0){
            viz[top.y]=1;
            s=s+ top.c;
            nrmuchii++;
            // Se adauga muchia la solutie
            apm.push_back(make_pair(top.x,top.y));

            // Se adauga in pq muchiile nodului curent
            for(int k=0; k<la[top.y].size(); k++){
                pq.push(muchie(top.y,la[top.y][k].first, la[top.y][k].second));
            }
        }
    }

    g<<s<<"\n"<<nrmuchii<<"\n";

    for(int l=0; l<apm.size(); l++){
        g<<apm[l].first<<" "<<apm[l].second<<"\n";
    }

    f.close();
    g.close();
    return 0;
}