#include <fstream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;

#define NMAX 200000

ifstream cin("apm.in");
ofstream cout("apm.out");

class DisjointSetUnion{
  private:
    int fat[NMAX], sz[NMAX];

  public:
     DisjointSetUnion(){
        memset(fat, 0, NMAX-1);
        memset(sz, 0, NMAX-1);
     }

    void make(int nod){
        fat[nod]=nod;
        sz[nod]=1;
    }

    void join(int noda, int nodb){
        int a=get(noda), b=get(nodb);
        if(a==b) return;
        if(sz[a]<sz[b]) swap(a, b);
        fat[b]=a;
        sz[a]+=sz[b];
    }

    int get(int nod){
        if(fat[nod]==nod) return nod;
        else return fat[nod]=get(fat[nod]);
    }
};

struct muchie{
    int a, b, c;

    bool operator<(muchie x){
        return c<x.c;
    }
};

DisjointSetUnion dsu;

int n, m;

vector<muchie> vec;
vector<muchie> sol;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int a, b, c;
        cin>>a>>b>>c;
        vec.push_back({a, b, c});
    }
    for(int i=1;i<=n;++i){
        dsu.make(i);
    }
    int cost=0;
    sort(vec.begin(), vec.end());
    for(auto i:vec){
        if(dsu.get(i.a)!=dsu.get(i.b)){
            dsu.join(i.a, i.b);
            sol.push_back(i);
            cost+=i.c;
        }
    }
    cout<<cost<<"\n";
    cout<<sol.size()<<"\n";
    for(auto i:sol){
        cout<<i.a<<" "<<i.b<<"\n";
    }
    return 0;
}