#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

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

int *t,*k;

struct triplu
{
    int a,b,cost;
};

bool comp (triplu i,triplu j) { return (i.cost<j.cost); }

int find_set(int x)
{
    if (t[x]==0) return x;
    t[x]=find_set(t[x]);
    return t[x];
}

int main()
{
    int n,m,cost=0,*c,j=0;
    vector <triplu> v;
    f>>n>>m;
    triplu x;
    for (int i=0;i<m;i++)
    {
        f>>x.a>>x.b>>x.cost;
        v.push_back(x);
    }
    sort(v.begin(),v.end(),comp);
    t=new int[n+1];
    k=new int[n+1];
    c=new int[n-1];
    for (register int i=1;i<=n;i++) t[i]=k[i]=0;
    for (register int i=0;i<m && j<n-1;i++)
        if (find_set(v[i].a)!=find_set(v[i].b))
        {
        if (k[v[i].a]<k[v[i].b]) t[find_set(v[i].a)]=find_set(v[i].b);
            else t[find_set(v[i].b)]=find_set(v[i].a);
        if (k[v[i].a]==k[v[i].b]) k[v[i].a]++;
        c[j]=i;
        j++;
        cost+=v[i].cost;
        }
    g<<cost<<"\n"<<n-1<<"\n";
    for (register unsigned int i=0;i<n-1;i++) g<<v[c[i]].a<<" "<<v[c[i]].b<<"\n";
    return 0;
}