#include <bits/stdc++.h>
using namespace std;

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

int n,m;
vector<tuple<int,int,int>> edges;

vector<int> p;

int find(int x);

inline void unite(int x, int y){
    p[find(x)]=find(y);
}

inline bool same(int x, int y){
    return find(x)==find(y);
}

int find(int x){
    if(p[x]==x){
        return x;
    }
    return p[x]=find(p[x]);
}

void kruscal(){
    for(int i=1;i<=n;++i)
        p[i]=i;
    sort(edges.begin(), edges.end());
    int cost=0;
    vector<tuple<int,int>> sol;
    for(auto t:edges){
        int x, y, c;
        tie(c,x,y)=t;
        if(!same(x,y)){
            unite(x,y);
            cost+=c;
            sol.push_back(make_tuple(x,y));
        }
    }
    fout<<cost<<"\n"<<sol.size()<<"\n";
    for(tuple<int,int> t:sol){
        int x,y;
        tie(x,y)=t;
        fout<<x<<" "<<y<<"\n";
    }
}

int main() {
    fin>>n>>m;
    p.resize(n+1,0);
    for(int k=m; k--;){
        int x,y,c;
        fin>>x>>y>>c;
        edges.push_back(make_tuple(c,x,y));
    }
    kruscal();
    return 0;
}