#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#define inf 2000000000

using namespace std;

struct graf
{
    int nod,c;
    bool operator <(const graf &aux) const
    {
        return c>aux.c;
    }
}aux;
priority_queue<graf> h;
vector<graf>v[200010];
vector<graf>::iterator it;
vector<pair<int,int> >vsol;
int cost[200010],tata[200010],n,m,i,x,y,sol;
char vaz[200010];

void introduceinapm(int nod)
{
    vaz[nod]=1;
    for(it=v[nod].begin();it!=v[nod].end();it++)
    {
        aux=*it;
        if(!vaz[aux.nod] && cost[aux.nod]>aux.c)
        {
            cost[aux.nod]=aux.c;
            tata[aux.nod]=nod;
            h.push(aux);
        }
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&aux.nod,&aux.c);
        v[x].push_back(aux);
        swap(x,aux.nod);
        v[x].push_back(aux);
    }
    for(i=1;i<=n;i++) cost[i]=inf;
    cost[1]=0;
    introduceinapm(1);
    for(i=1;i<n;i++)
    {
        do
        {
            aux=h.top();
            h.pop();
        }while(cost[aux.nod]!=aux.c);
        sol+=aux.c;
        vsol.push_back(make_pair(tata[aux.nod],aux.nod));
        introduceinapm(aux.nod);
    }
    printf("%d\n%d\n",sol,n-1);
    for(i=0;i<n-1;i++) printf("%d %d\n",vsol[i].first,vsol[i].second);
    return 0;
}