#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;

vector <tuple<int,int,int> > muchii;
priority_queue <tuple<int,int,int> > heap;
int tata[200005];
int dist[200005];
int find_father(int x)
{
    if(x==tata[x])
        return x;
    return find_father(tata[x]);
    tata[x]=tata[tata[x]];
}
void unite(int x, int y)
{
    if(dist[x]>dist[y])
        tata[y]=tata[x];
    else
        tata[x]=tata[y];
    if(dist[x]==dist[y])
        dist[y]++;
}
int kruskal(int N, int M)
{
    int x,y,c,i=0,cost=0;
    tuple <int,int,int> tuplu;
    while(i<N-1)
    {
        tuplu=heap.top();
        heap.pop();
        get<0>(tuplu)=-get<0>(tuplu);
        x=get<1>(tuplu);
        y=get<2>(tuplu);
        c=get<0>(tuplu);
        if(find_father(x)!=find_father(y))
        {
            cost+=c;
            muchii.push_back(make_tuple(c,x,y));
            i++;
            unite(find_father(x),find_father(y));
        }
    }
    return cost;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int i,N,M,x,y,c;
    f>>N>>M;
    for(i=1;i<=N;i++)
    {
        tata[i]=i;
        dist[i]=1;
    }
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        heap.push(make_tuple(-c,x,y));
    }
    g<<kruskal(N,M)<<endl;
    int lim=muchii.size();
    g<<lim<<endl;
    for(i=0;i<lim;i++)
        g<<get<1>(muchii[i])<<" "<<get<2>(muchii[i])<<endl;
    return 0;
}