#include<iostream>
#include<algorithm>
#include<vector>
#include <fstream>
#include <limits.h>

using namespace std;

const int maxn = 200200;

int *p,cost,*cheie,*h,*poz,n,m,l;
vector <pair<int,int> > Q[maxn],A;

void actualizare(int x)
{
    int nod,cost;
    for(unsigned int i=0;i<Q[x].size();++i)
    {
        nod = Q[x][i].first;
        cost = Q[x][i].second;
        if (cost<cheie[nod])
        {
            cheie[nod]=cost;
            p[nod]=x;
        }
    }
}

void min_heapify(int i)
{
    while ( (i*2<=l && cheie[h[i]]>cheie[h[i*2]]) || (i*2+1<=l && cheie[h[i]]>cheie[h[i*2+1]]) )
    {
        if (cheie[h[i*2]] < cheie[h[i*2+1]] || i*2+1>l)
        {
            swap(h[i],h[i*2]);
            swap(poz[h[i]],poz[h[i*2]]);
            i=i*2;
        }
        else
        {
            swap(h[i],h[i*2+1]);
            swap(poz[h[i]],poz[h[i*2+1]]);
            i=i*2+1;
        }
    }
}


void reverse_heapify(int i)
{
    while (i>1 && cheie[h[i]]<cheie[h[i/2]])
    {
        swap(h[i],h[i/2]);
        swap(poz[h[i]],poz[h[i/2]]);
        i=i/2;
    }
}

int decapitare()
{
    int x = h[1];
    swap(h[1],h[l]);
    swap(poz[h[1]],poz[h[l]]);
    l--;
    min_heapify(1);
    poz[x] = 0;
    return x;
}

void citire()
{
    ifstream f("apm.in");
    f>>n>>m;
    int x,y,c;
    for(int i=0;i<m;++i)
    {
        f>>x>>y>>c;
        Q[x].push_back(make_pair(y,c));
        Q[y].push_back(make_pair(x,c));
    }
    cheie=new int[maxn];
    for(int i=1;i<=n;++i)
        cheie[i] = INT_MAX;
    cheie[1] = 0;
}

int main()
{
    citire();
    p=new int[maxn];
    actualizare(1);
    poz=new int[maxn];
    h=new int[2*maxn+100];
    for(int i=2;i<=n;i++)
      {
          l++;
          h[l] = i;
          poz[i] = l;
          reverse_heapify(l);
      }
    for(int i=0;i<n-1;i++)
    {
        int x = decapitare();
        actualizare(x);
        cost+=cheie[x];
        A.push_back(make_pair(x,p[x]));
        for(unsigned int j=0;j<Q[x].size();++j)
        {
            int nod = Q[x][j].first;
            if (poz[nod]) reverse_heapify(poz[nod]);
        }
    }
    ofstream g("apm.out");
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;++i)
        g<<A[i].first<<" "<<A[i].second<<"\n";
    /*Avem un heap h si un vector poz unde poz[i]=indicele lui h pentru care h[i]=i
    in Q retinem muchiile grafului iar in A muchiile arborelui
    p este vectorul de tati iar cheie retine costul fiecarui nod
    algoritmul functioneaza cu ajutorul procedurilor standard ale unui heap
    */
    return 0;
}