#include <bits/stdc++.h>
#define N 200005
#define M 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,s;
int t[N],h[N];
struct muchii
{
    int x,y,c;
}edges[M];
vector<muchii>sol;
bool ordo(muchii a,muchii b)
{
    return a.c<b.c;
}
int Find(int a)
{
    if(!t[a]) return a;
    return t[a]=Find(t[a]);
}
void Union(int a, int b)
{
    int x=Find(a);
    int y=Find(b);
    if(x==y) return;
    if(h[x]<h[y]) t[x]=y;
    else if(h[x]>h[y]) t[y]=x;
    else t[x]=y, h[y]++;
}
int main() {
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>edges[i].x>>edges[i].y>>edges[i].c;
    sort(edges+1,edges+m+1,ordo);
    for(int i=1; i<=m; i++)
        if(Find(edges[i].x)!=Find(edges[i].y)) { Union(edges[i].x,edges[i].y);
                                                 s+=edges[i].c; sol.push_back(edges[i]);
                                               }
    fout<<s<<"\n";
    fout<<sol.size()<<"\n";
    for(auto afis:sol) fout<<afis.x<<" "<<afis.y<<"\n";
    return 0;
}