#include <bits/stdc++.h>
using namespace std;
class DisjointSet{
private:
    int Size;
    int *Rank,*Parent;
    void Init(){
        for(int i=1;i<=Size;++i){
            Rank[i]=1;
            Parent[i]=i;
        }
    }
public:
    DisjointSet(int Size):Size{Size},Rank{new int[Size+1]},Parent{new int[Size+1]}{
        Init();
    }
    int Find(int x){
        int Root=x;
        while(Parent[Root]!=Root)
            Root=Parent[Root];
        while(x!=Root){
            int next=Parent[x];
            Parent[x]=Root;
            x=next;
        }
        return Root;
    }
    void Unite(int x,int y){
        int xRoot=Find(x),yRoot=Find(y);
        if(xRoot!=yRoot){
            if(Rank[xRoot]>Rank[yRoot])
                Parent[yRoot]=xRoot;
            else{
                if(Rank[xRoot]==Rank[yRoot])
                    ++Rank[yRoot];
                Parent[xRoot]=yRoot;
            }
        }
    }
    bool Connected(int x,int y){
        return Find(x)==Find(y);
    }
};
struct Edge{
    int st,dr,cost;
    bool operator <(const Edge &other) const{
        return cost<other.cost;
    }
    void Read(){
        scanf("%d %d %d",&st,&dr,&cost);
    }
}E[400005];
vector<Edge> Ans;
DisjointSet A(200000);
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
        E[i].Read();
    sort(E+1,E+m+1);
    int costMin=0;
    for(int i=1;i<=m;++i){
        if(A.Find(E[i].st)!=A.Find(E[i].dr)){
            costMin+=E[i].cost;
            A.Unite(E[i].st,E[i].dr);
            Ans.push_back(E[i]);
        }
    }
    printf("%d\n",costMin);
    printf("%d\n",n-1);
    for(auto it:Ans)
        printf("%d %d\n",it.st,it.dr);
    return 0;
}