#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct mazan
{
    int a,b,c;
};
mazan v[400001];
int tata[200001],sum;
vector < pair<int,int> > afis[200001];
int radacina(int val)
{
    if(tata[val]==0)
        return val;
    tata[val]=radacina(tata[val]);
    return tata[val];
}
bool cmp(mazan a,mazan b)
{
    if(a.c<b.c)
        return 1;
    return 0;
}
void reuniune(int a,int b,int c)
{
    int rx=radacina(a),ry=radacina(b);
    if(rx==ry)
        return;
    sum+=c;
    tata[ry]=rx;
    for(int i=0;i<(int)afis[ry].size();i++)
        afis[rx].push_back({afis[ry][i].first,afis[ry][i].second});
    afis[rx].push_back({a,b});
    afis[ry].clear();
}
int main()
{
    int n,m,i;
    in>>n>>m;
    for(i=1; i<=m; i++)
        in>>v[i].a>>v[i].b>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(i=1; i<=m; i++)
        reuniune(v[i].a,v[i].b,v[i].c);
    int x=radacina(1);
    out<<sum<<'\n'<<n-1<<'\n';
    for(i=0;i<(int)afis[x].size();i++)
        out<<afis[x][i].first<<" "<<afis[x][i].second<<'\n';
    return 0;
}