#include <bits/stdc++.h>
#define NM 200005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,t[NM],last[NM];
struct muchii{int x,y,c;};
muchii v[2*NM];
vector <pair<int,int>> sol;

void Read();
void Kruskal();
void Add(int,int);
int findRad(int);
bool cmp(muchii a,muchii b) {return a.c<b.c;}

int main()
{   Read();
    Kruskal();
    return 0;
}

void Read()
{   f>>n>>m;
    for(int i=1; i<=m; i++)
    {   f>>v[i].x>>v[i].y>>v[i].c;
        t[v[i].x]=last[v[i].x]=v[i].x;
        t[v[i].y]=last[v[i].y]=v[i].y;
    }
}

void Kruskal()
{   sort(v+1,v+m+1,cmp);
    int sMin=0;
    for(int i=1; i<=m; i++)
        if(findRad(v[i].x)!=findRad(v[i].y))
        {   sMin+=v[i].c;
            sol.push_back({v[i].x,v[i].y});
            Add(v[i].x,v[i].y);
        }
    int lg=sol.size();
    g<<sMin<<'\n'<<lg<<'\n';
    for(int i=0; i<lg; i++)
        g<<sol[i].second<<' '<<sol[i].first<<'\n';
}

void Add(int x,int y)
{   int r1=findRad(x),r2=findRad(y);
    t[r2]=last[r1];
    last[r1]=last[r2];
    t[last[r1]]=t[last[r2]];
}

int findRad(int nod)
{   int k=nod;
    while(k!=t[k]) k=t[k];
    while(nod!=t[nod])
    {   nod=t[nod];
        t[nod]=k;
    }
    return nod;
}