#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

struct muchie
{
    int x,y;
    int cost;
    friend bool operator>(const muchie&u1,const muchie&u2);

};


bool operator>(const muchie&u1,const muchie&u2)
{
        return u1.cost>u2.cost;
};
vector <muchie> sol;
priority_queue <muchie, vector<muchie>, greater <muchie> > H;

int n,m;
int tata[200001];
long int cst=0;

void citire()
{
    scanf("%d%d",&n,&m);
    muchie u;
    for(int i=0;i<m;i++)
       {
           scanf("%d%d%d",&u.x,&u.y,&u.cost);
           H.push(u);
       }
}

int find(int x)
{
    int r=x;
    while(tata[r]!=r)
       r=tata[r];
    //comprim drumul
    int y=x;
    while(y!=r)
    {
        int aux=tata[y];
        tata[y]=r;
        y=aux;
    }
    return r;
}

void unesc(int c1, int c2)
{
    tata[c1]=c2;
}

void kruskal()
{
    for(int i=1;i<=n;i++) tata[i]=i;
    int i=0,k=0;
//printf("%d \n",n);
    while(sol.size()<n-1)
    {
        muchie u;
        u=H.top();
        H.pop();
        //printf("%d %d %d\n",u.x,u.y,u.cost);
        int c1=find(u.x);
        int c2=find(u.y);
        if(c1!=c2)
        {
            cst+=u.cost;
            sol.push_back(u);
            unesc(c1,c2);
        }
    }
}

void afisare()
{
    //printf("%ld\n%d\n",cst,n-1);
    cout<<cst<<endl<<n-1<<endl;
    for(int i=0;i<n-1;i++)
      // printf("%d %d %d\n",sol[i].x,sol[i].y,sol[i].cost);
      printf("%d %d\n",sol[i].x,sol[i].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    kruskal();
    afisare();
    return 0;
}