#include <fstream>
#include <algorithm>
#include <vector>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define nmax 400000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,t[nmax],cost;
vector<pair<int, int> > sol;
vector<pair<int, pair<int, int> > > u;

int rad(int nod){
    if(t[nod]!=nod) t[nod]=rad(t[nod]);
    return t[nod];
}

void kruskal(){
    int n1,n2;
    for(int i=0; i<=n; i++)
        t[i]=i;
    for(int i=0; i<=m; i++)
    {
        n1=u[i].s.f;
        n2=u[i].s.s;
        if(rad(n1)!=rad(n2))
        {
            cost+=u[i].f;
            sol.pb(mp(n1,n2));
            t[t[n2]]=t[n1];
        }
    }
}
int main(){
    int x,y,c;
    f>>n>>m;
    for(int i=0; i<m; i++){
        f>>x>>y>>c;
        u.pb(mp(c,mp(x,y)));
    }
    sort(u.begin(),u.end());
    kruskal();
    g<<cost<<'\n'<<sol.size()<<'\n';
    for(int i=0; i<sol.size(); i++){
        g<<sol[i].s<<' '<<sol[i].f<<'\n';
    }
}