#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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


vector <int> l[200001];
pair <int , int> v[400001],afis[400001];
int cost[400001];
int tata[200001];

struct{
    int x,y,cost;
    bool operator <(const muchie &A)const{
        return const<a.cost;
    }
}muchie[400001];

void viz0(int n){
    for(int i=1;i<=n;i++)
            tata[i]=-1;
}


void sortare(int m){
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
            if(cost[j]<cost[i])
                swap(cost[i],cost[j]),swap(v[i],v[j]);
}

int find_root(int node){
    if(tata[node]<0)
        return node;
    int root=find_root(tata[node]);
    tata[node]=root;
    return root;
}

void roots_union(int x, int y){
    int r_x=find_root(x);
    int r_y=find_root(y);
    if(tata[r_x]<tata[r_y]){
        swap(r_y,r_x);
    }
    tata[r_y]+=tata[r_x];
    tata[r_x]=r_y;
}

int main() {
    int n,m;
    int x,y,z;
    int s=0,k=0;


    fin>>n>>m;
    viz0(n);
    for(int i=1;i<=m;i++){
        fin>>muchie.x>>muchie.y>>muchie.cost;
    sort(muchie+1,muchie+m+1)

    for(int i=1;i<=m;i++){
        if(find_root(muchie.x)!=find_root(muchie.y)){
            k++;
            s+=muchie.cost;
            afis[k].first=muchie.y;
            afis[k].second=muchie.x;
            roots_union(muchie.x,muchie.y);
        }
    }
    fout<<s<<endl<<k<<endl;
    for(int i=1;i<=k;i++)
        fout<<afis[i].first<<" "<<afis[i].second<<endl;
    return 0;
}