#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

int t[200005],h[200005];

int FindSet(int x)
{
    if(t[x]==x)
        return x;
    else
        return t[x]=FindSet(t[x]);

}

void Union(int x,int y)
{
    int a,b;
    a=FindSet(x);
    b=FindSet(y);

    if(h[a]<h[b])
        t[a]=b;
    else
        t[b]=a;

    if(h[a]==h[b])
        h[b]++;
}

bool cmp( pair< int,pair<int,int> >  a, pair< int,pair<int,int> >b )
{
    return(a.first<b.first);
}

int main()
{
    int i,n,m,sum=0;
    vector< pair< int,pair<int,int> > > edges;
    vector<pair<int,int> > tree;
    ifstream f("apm.in");
    ofstream g("apm.out");

    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        edges.push_back(make_pair(cost,make_pair(x,y)));
    }

    sort(edges.begin(),edges.end(),cmp);

    for(i=1; i<=n; i++)
    {
        t[i]=i;
        h[i]=0;
    }

    for(i=0; i<m; i++)
    {
        int a,b;
        a=edges[i].second.first;
        b=edges[i].second.second;
        if(FindSet(a)!=FindSet(b))
        {
            sum+=edges[i].first;
            Union(a,b);
            tree.push_back(make_pair(b,a));
        }
    }

    g<<sum<<"\n"<<tree.size()<<"\n";
    for(i=0; i<tree.size(); i++)
        g<<tree[i].first<<" "<<tree[i].second<<"\n";

    return 0;
}