#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

const int maxn = 200200;
const int INF = 200000200;

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

void introduce_in_apm(int x)
{
    for(int i=0;i<Q[x].size();++i)
    {
        int nod = Q[x][i].first;
        int cost = Q[x][i].second;
        cheie[nod] = min(cheie[nod],cost);
        if (cheie[nod] == cost)
            p[nod] = x; //tatal lui nod este x
    }
}

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


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

int scoate_radacina_h()
{
    int x = h[1]; //scoatem radacina
    swap(h[1],h[l]); //o inlocuim cu ultimul element din arbore
    swap(poz[h[1]],poz[h[l]]);
    l--; //scadem numarul de elemente din arbore
    push(1); //se reorganizeaza arborele in functie de chei
    poz[x] = 0;
    return x;
}

void citire()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        scanf("%d %d %d",&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] = INF;
    cheie[1] = 0;
}

int main()
{

    citire();
    p=new int[maxn];

    introduce_in_apm(1);

    poz=new int[maxn];
    h=new int[2*maxn+100];

    for(int i=2;i<=n;++i)
      {
          h[++l] = i; //adaugam nodurile in heap si le retinem pozitia
          poz[i] = l;
          pop(l); //rearanjeaza nodurile in functie de cheile lor in heap
      }


    for(int i=1;i<n;++i)
    {
        int x = scoate_radacina_h(); //minimul
        introduce_in_apm(x);
        cost+=cheie[x]; //marim costul
        A.push_back(make_pair(x,p[x])); //introducem in solutia noastra pe x alaturi de tatal lui
        for(int j=0;j<Q[x].size();++j) //stergem elementul x din arbore
        {
            int nod = Q[x][j].first; //pentru fiecare muchie de care era legat
            if (poz[nod]) //daca inca exista in arbore
                pop(poz[nod]);
        }
    }
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(unsigned int i=0;i<n-1;++i)
        printf("%d %d\n",A[i].first,A[i].second);
    return 0;
}