#include <fstream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
//ifstream f("apm.in");
//ofstream g("apm.out");
struct tripleta{
int t,x,c;
};
vector<pair<int,int> >sol;

struct compar{
 bool operator()(tripleta a,tripleta b)
{
    return b.c<a.c;
}
};
priority_queue<tripleta,vector<tripleta>, compar>H;
int n,m,ct,viz[200001];
vector<pair<int,int> >B[200001];
int main()
{
    int i,nr,z,x,y,c;
    tripleta e;
    //f>>n>>m;
    fscanf(f,"%d %d",&n,&m);

    for(i=1;i<=m;i++)
    {
        //f>>e.x>>e.y>>e.c;
         fscanf(f,"%d %d %d",&x,&y,&c);
         B[x].push_back(make_pair(y,c));

         B[y].push_back(make_pair(x,c));
    }
    ct=0; nr=0;
    viz[1]=1;
    for(i=0;i<B[1].size();i++)
    {
        e.t=1;
        e.x=B[1][i].first;
        e.c=B[1][i].second;
        H.push(e);
    }
    while(nr<n-1)
    {
        e=H.top();
        H.pop();
        int z=e.x;
        if(viz[z]==0)
        {
            nr++;
            viz[z]=1;
            sol.push_back(make_pair(z,e.t));
            ct=ct+e.c;
            for(i=0;i<B[z].size();i++)
                {
                    pair<int,int> p=B[z][i];
                    if(!viz[p.first])
                        {
                            e.x=p.first;
                            e.t=z;
                            e.c=p.second;
                            H.push(e);
                        }
                }
        }
    }
    //g<<ct<<endl;
    fprintf(g,"%d\n",ct);
    //g<<n-1<<endl;
    fprintf(g,"%d\n",n-1);
    for(i=0;i<sol.size();i++)
        //g<<sol[i].first<<' '<<sol[i].second<<endl;
        fprintf(g,"%d %d\n",sol[i].first,sol[i].second);
    return 0;
}