#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x,y;
    int c;
};

int n,m;
muchie v[400001];
int gr[200001];
bool cmp(muchie a,muchie b)
{
    return a.c < b.c;
}

queue <pair <int,int> > q;


int main()
{
    f>>n>>m;
    int i,j;
    for(i=1;i<=n;i++)
        gr[i]=i;
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,cmp);
    int nr=0,k;
    long long int s=0;
    for(i=1;i<=m,nr<n-1;i++)
    {
        if(gr[v[i].x]!=gr[v[i].y])
       {
           nr++;
           q.push(make_pair(v[i].x,v[i].y));
           s+=v[i].c;
           k=gr[v[i].y];
           for(j=1;j<=n;j++)
                if(gr[j]==k)
                    gr[j]=gr[v[i].x];
       }
    }
    g<<s<<"\n"<<n-1<<"\n";
    while(q.empty()==false)
    {
        g<<q.front().first<<" "<<q.front().second<<"\n";
        q.pop();
    }
    return 0;
}