#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200005
using namespace std;
ifstream f;
ofstream g;
struct edge{
    int x,y,c;
};
vector<edge> L;
vector<pair<int,int>> ans;
int n,m,apm,rang[nmax],rep[nmax];
bool cmp(edge A,edge B)
{
    return A.c<B.c;
}
int reprezentant(int x)
{
    if(!rep[x])
        return x;
    rep[x]=reprezentant(rep[x]);
    return rep[x];
}
void unire(int x,int y)
{
    if(rang[x]==rang[y])
    {
        rang[x]++;
        rep[y]=x;
    }
    else if(rang[x]<rang[y])
        rep[x]=y;
    else rep[y]=x;
}
int main()
{
    f.open("apm.in");
    g.open("apm.out");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        L.push_back({x,y,c});
    }
    sort(L.begin(),L.end(),cmp);
    for(auto a:L)
    {
        int rx=reprezentant(a.x);
        int ry=reprezentant(a.y);
        if(rx!=ry)
        {
            apm+=a.c;
            ans.push_back(make_pair(a.x,a.y));
            unire(rx,ry);
        }
    }
    g<<apm<<'\n'<<n-1<<'\n';
    for(auto a:ans)
        g<<a.first<<" "<<a.second<<'\n';
    f.close();
    g.close();
    return 0;
}