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

using namespace std;

int rang[200005],tata[200005];
priority_queue <tuple<int,int,int> > heap;
vector <pair<int,int> > muchii;
int find_father(int nod)
{
    if(nod==tata[nod])
        return nod;
    int x=find_father(tata[nod]);
    tata[nod]=x;
    return x;
}
void unite(int x, int y)
{
    if(rang[x]>rang[y])
        tata[y]=x;
    if(rang[y]>=rang[x])
        tata[x]=y;
    if(rang[y]==rang[x])
        rang[y]++;
}
int kruskal(int N)
{
    int x,y,tx,ty,c,cost=0,nr_muchii=0;
    tuple<int,int,int> tuplu;
    while(nr_muchii!=N-1)
    {
        tuplu=heap.top();
        heap.pop();
        c=-get<0>(tuplu);
        x=get<1>(tuplu);
        y=get<2>(tuplu);
        tx=find_father(x);
        ty=find_father(y);
        if(tx!=ty)
        {
            muchii.push_back(make_pair(x,y));
            cost+=c;
            unite(tx,ty);
            nr_muchii++;
        }
    }
    return cost;
}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    int N,M,x,y,c,i,cost;
    in>>N>>M;
    for(i=1;i<=N;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    for(i=1;i<=M;i++)
    {
        in>>x>>y>>c;
        heap.push(make_tuple(-c,x,y));
    }
    cost=kruskal(N);
    out<<cost<<"\n";
    out<<N-1<<"\n";
    for(i=0;i<N-1;i++)
        out<<muchii[i].first<<" "<<muchii[i].second<<"\n";
    return 0;
}