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

#define inf 1500
#define MAXN 200001
using namespace std;

int viz[100],prec[100],d[100];

fstream f, out;

typedef struct{
    int v;
    int value;
}node;

bool operator<(node a, node b)
{
    return (a.value > b.value);
}

vector<node> cost[MAXN];
priority_queue<node> q;
vector<int> apm[MAXN];

int get_cost(int n1, int n2)
{
    for(unsigned int i=0;i<cost[n1].size();i++)
    {
        if(cost[n1][i].v == n2)
            return cost[n1][i].value;
    }
    return 0;
}

int prim(int root,int n)
{
    bool appeared[MAXN];
    int cuost =0;
    int d[MAXN],p[MAXN],ma=0;

    for(int i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
        p[i]=-1;
        appeared[i]=false;
    }

    d[root]=0;

    node nod;
    nod.v = root;
    nod.value = 0;
    q.push(nod);

    while(!q.empty())
    {
        while(appeared[q.top().v]==true)
        {
            q.pop();
        }
        if(appeared[q.top().v]==false)
        {
            nod.v = q.top().v;
            nod.value = q.top().value;
            q.pop();
        }
        appeared[nod.v]=true;

       // cout<<"["<<nod.v<<","<<p[nod.v]<<"] ";
        if(nod.v != -1 && p[nod.v]!=-1)
            apm[nod.v].push_back(p[nod.v]);

        cuost += get_cost(nod.v, p[nod.v]);
        ma++;//adauga muchia

        for(int i=0;i<cost[nod.v].size();i++)
        {
            if(cost[nod.v][i].value < d[cost[nod.v][i].v])
            {
                d[cost[nod.v][i].v] = cost[nod.v][i].value;
                p[cost[nod.v][i].v] = nod.v;

                node v;
                v.v =cost[nod.v][i].v;
                v.value=cost[nod.v][i].value;
                q.push(v);
            }
        }
    }
    out<<cuost<<endl;
    return ma;
}

int main()
{
    int m,n,i,j,x,y,x0;

    f.open("apm.in",ios::in);
    out.open("apm.out", ios::out);
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        int val;
        f>>val;
        node nod;
        nod.v = y;
        nod.value=val;
        cost[x].push_back(nod);
        nod.v = x;
        cost[y].push_back(nod);
    }

    out<<prim(1,n)-1<<endl;

    for(i=1;i<=n;i++)
        for(j=0;j<apm[i].size();j++)
        {
            out<<i<<" "<<apm[i][j]<<endl;
        }

}