#include <fstream>
#include <vector>
#define nmax 200000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y,c;
};
int n,m,t[nmax+5],cost,r[nmax+5];
vector<muchie> g;
vector < pair <int, int > > ans;
void quicksort(int st, int dr)
{
    int i=st, j=dr;
    muchie mid=g[(st+dr)>>1],tmp;
    while(i<=j)
    {
        while(g[i].c<mid.c)
            i++;
        while(g[j].c>mid.c)
            j--;
        if(i<=j)
        {
            tmp=g[i];
            g[i]=g[j];
            g[j]=tmp;
            i++;
            j--;
        }
    }
    if(st<j)
        quicksort(st,j);
    if(i<dr)
        quicksort(i,dr);
}
int tata(int x)
{
    int i,y;
    for(i=x;i!=t[i];i=t[i]);
    while(x!=t[x])
    {
        y=t[x];
        t[x]=i;
        x=y;
    }
    return i;
}
void unite(int x,int y)
{
    r[x]>r[y]?t[y]=x:t[x]=y;
    r[y]+=(r[x]==r[y]);
}
int main()
{
    fin>>n>>m;
    int x,y,c;
    g.push_back({0,0,0});
    for(int i=1;i<=m;i++)
    {
       fin>>x>>y>>c;
       g.push_back({x,y,c});
    }
    quicksort(1,m);
    for(int i=1;i<=n;i++)
        t[i]=i,r[i]=1;
    for(int i=1;i<=m;i++)
    {
        x=tata(g[i].x);
        y=tata(g[i].y);
        if(x!=y)
        {
            cost+=g[i].c;
            ans.push_back({g[i].x,g[i].y});
            unite(x,y);
        }
    }
    fout<<cost<<"\n";
    fout<<n-1<<"\n";
    for(int i=0;i<ans.size();i++)
        fout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}