#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Edge{
    int x,y,cost;

    Edge(){}
    Edge(int x, int y, int cost){
        this->x=x;
        this->y=y;
        this->cost=cost;
    }
    bool operator<(const Edge &other) const { return this->cost<other.cost; }
};
int n,m,x,y,z;
int costMinim;
vector<Edge> edgeList;
vector<Edge> answer;
vector<int> parent;
vector<int> rang;

int find(int x){
    int R,y;
    for(R=x;parent[R]!=R;R=parent[R]);
    for(;parent[x]!=R;){
        y=parent[x];
        parent[x]=R;
        x=y;
    }
    return R;
}

void unite(int x,int y){
    if(rang[x]>rang[y])
        parent[y]=x;
    else{
        parent[x]=y;
        rang[y]=(rang[x]==rang[y]) ? rang[y]+1:rang[y];
    }
}

int main()
{
    fin>>n>>m;
    parent.resize(n+1);
    for(int i=1;i<=n;i+=1)parent[i]=i;
    rang.resize(n+1);
    fill(rang.begin(),rang.end(),1);
    edgeList.resize(m);
    for(int i=0;i<m;i+=1){
        fin>>x>>y>>z;
        edgeList[i]=Edge(x,y,z);
    }
    sort(edgeList.begin(),edgeList.end());
    for(int i=0;i<m;i+=1){
        x=edgeList[i].x;
        y=edgeList[i].y;
        if(find(x)!=find(y)){
            costMinim+=edgeList[i].cost;
            answer.push_back(edgeList[i]);
            unite(find(x),find(y));
        }
    }
    fout<<costMinim<<'\n'<<answer.size()<<'\n';
    for(vector<Edge>::iterator it=answer.begin();it!=answer.end();it++){
        fout<<it->y<<' '<<it->x<<'\n';
    }
    return 0;
}