#include <bits/stdc++.h>
#define Dim 200006
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int N,M,a,b,c,ans,nr;
bool stop=1,viz[Dim];
typedef struct muchie
{
    int c1,c2,cost;
} tym;

tym val;

struct cmp
{
    bool operator() (tym x,tym y)
    {
        if(x.cost>=y.cost)
            return 1;
        else return 0;
    }
};
vector < pair<int,int> > V[Dim];
queue < pair<int,int> > qu;
priority_queue < tym,vector<tym>,cmp > minheap;

int main()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>a>>b>>c;
        V[a].push_back({b,c});
        V[b].push_back({a,c});

    }
    nr=N-1;
    viz[1]=1;
    while(nr)
    {

    bool ok=1;
    while(ok==1&&!minheap.empty()&&stop==0)
    {
        val=minheap.top();
        minheap.pop();
        if(!viz[val.c2])
        {
            ok=0;
            viz[val.c2]=1;
            ans+=val.cost;
            qu.push({val.c1,val.c2});
            nr--;
        }
    }
    if(stop==1) val.c2=1;
    stop=0;
    for(unsigned int i=0;i<V[val.c2].size();i++)
    {
        int vecin=V[val.c2][i].first;
        int cost=V[val.c2][i].second;
        if(!viz[vecin])
        {
            minheap.push({val.c2,vecin,cost});
        }
    }

    }
    g<<ans<<'\n'; g<<N-1<<'\n';
    while(!qu.empty())
    {
        g<<qu.front().first<<" "<<qu.front().second<<'\n';
        qu.pop();
    }
}