///prim
#include <stdio.h>
#include <vector>
#include <queue>
#define N 200005
#define OK printf("OK");
using namespace std;
struct muchie
{
    int nod,cost;
}aux;
struct lat
{
    int x,y,cost;
};
struct minheap
{
    bool operator()(lat a,lat b)
    {
        return a.cost>b.cost;
    }
};

vector<muchie> g[N];
int n,m,i,x,y,cost,k,cost_total;
lat arb[N];
bool viz[N];
priority_queue<lat,vector<lat>,minheap> heap;

void add_edges(int x)
{
    viz[x]=true;
    for(int i=0;i<g[x].size();i++)
        if(!viz[g[x][i].nod])
        {
            heap.push({x,g[x][i].nod,g[x][i].cost});
        }

}
int main()
{
    FILE *f1,*f2;
    f1=fopen("apm.in","r");
    f2=fopen("apm.out","w");

    fscanf(f1,"%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(f1,"%d%d%d",&x,&y,&cost);
        g[x].push_back({y,cost});
        g[y].push_back({x,cost});
    }

    k=1;
    add_edges(1);
    while(!heap.empty() && k<n)
    {
        x=heap.top().x;
        y=heap.top().y;
        cost=heap.top().cost;
        heap.pop();

        if(!viz[y])
        {
            add_edges(y);
            cost_total+=cost;
            arb[k++]=heap.top();
        }
    }

    fprintf(f2,"%d\n%d\n",cost_total,n-1);
    for(i=1;i<n;i++)
        fprintf(f2,"%d %d\n",arb[i].x,arb[i].y);



    return 0;
}