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

using namespace std;

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

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

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

int uniune(int *t,int x,int y)
{
    if (find_set(t,x)!=find_set(t,y))
    {
        t[find_set(t,x)]=find_set(t,y);
        return 1;
    }
    return 0;
}

int main()
{
    int n,m;
    vector <pair<int,int> > muchii;
    vector <triplu> v;
    ifstream f("apm.in");
    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);
    int cost=0,*t,j=0;
    t=new int[n+1];
    for (int i=1;i<=n;i++) t[i]=0;
    for (int i=0;i<n-1;i++)
    {
        while (uniune(t,v[j].a,v[j].b)==0) j++;
        muchii.push_back(make_pair(v[j].a,v[j].b));
        cost+=v[j].cost;
        j++;
    }
    ofstream g("apm.out");
    g<<cost<<endl<<n-1<<endl;
    for (int i=0;i<muchii.size();i++) g<<muchii[i].first<<" "<<muchii[i].second<<endl;
    return 0;
}