#include <fstream>
#include <vector>
#include <algorithm>
#define mp make_pair
#define pb push_back
#define f first
#define s second

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,t[400000],cost;
bool sel[400000];
vector <pair <int, pair<int, int> > > l;
void leaga(int i,int j)
{
    int k;
    i=t[i];
    j=t[j];
    if(i==j)
        return;
    for(k=1;k<=n;k++)
        if(t[k]==i)
            t[k]=j;
}

void kruskal()
{
    int i,j,k,c;
    for(i=1;i<=n;i++)
        t[i]=i,sel[i]=false;
    for(k=0;k<=m;k++)
    {
        i=l[k].s.f;
        j=l[k].s.s;
        c=l[k].f;
        if(t[i]==t[j])
            continue;
        leaga(i,j);

    cost+=c;
    sel[i]=true;
    }
    fout<<cost<<"\n"<<n-1<<"\n";
}
int main()
{
    int  x,y,c,i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        l.pb(mp(c,mp(x,y)));
    }
    sort(l.begin(),l.end());
    kruskal();
    for(i=1;i<=m;i++)
        if(sel[i])
            fout<<l[i].s.f<<" "<<l[i].s.s<<"\n";

    return 0;
}