#include <cstdio>
#include <iostream>
#include <algorithm>
#define nmax 200005
#define inf 0x3f3f3f3f

using namespace std;

struct lst
{
    int nod, weight;
    lst *next;
};

class Graph
{

public:

    lst *g[nmax];

    void AddNode(int x,int y,int w)
    {
        if (g[x] == NULL)
        {
            g[x] = new lst;
            g[x] -> nod = y;
            g[x] -> weight = w;
            g[x] -> next = NULL;
        }
        else
        {
            lst *p;
            p = g[x];
            while(p -> next != NULL)
                p = p -> next;
            p -> next = new lst;
            p -> next -> nod = y;
            p -> next -> weight = w;
            p -> next -> next = NULL;
        }
    }
};

struct heap
{
    int nod,weight;
};

class PriorityQueue
{

public:

    heap a[nmax];
    int poz[nmax],sze,lbls;

    void DecreaseValue(int x,int w)
    {
        int i = poz[x];
        a[i].weight = w;
        while(i > 1 && a[i].weight < a[i / 2].weight)
        {
            swap(a[i],a[i / 2]);
            poz[a[i].nod] = i;
            poz[a[i / 2].nod] = i / 2;
            i = i / 2;
        }
    }

   void heapify(int i)
   {
        int smallest = i;
        if(2 * i <= sze && a[2 * i].weight < a[smallest].weight)
            smallest = 2 * i;
        if(2 * i + 1 <= sze && a[2 * i + 1].weight < a[smallest].weight)
            smallest = 2 * i + 1;
        swap(a[smallest],a[i]);
        poz[a[smallest].nod] = smallest;
        poz[a[i].nod] = i;
        if(smallest != i)
            heapify(smallest);
   }

    heap Pop()
    {
        heap x = a[1];
        swap(a[1],a[sze]);
        poz[a[1].nod] = 1;
        poz[a[sze].nod] = sze;
        sze--;
        heapify(1);
        return x;
    }

    void MakeHeap(int n,int d[])
    {
        sze = n;
        for(int i = 1;i <= n;i++)
        {
            a[i].nod = i;
            a[i].weight = d[i];
            poz[i] = i;
        }
        lbls = n;
    }

    bool Empty()
    {
        return (sze == 0);
    }

};

int n,m,d[nmax],pi[nmax],viz[nmax];
Graph grp;
PriorityQueue q;

void citire()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        grp.AddNode(x,y,c);
        grp.AddNode(y,x,c);
    }
    for(int i = 1; i <= n; i++)
        d[i] = inf;
}

void prim()
{
    int k;
    d[1] = 0;
    pi[1] = -1;
    q.MakeHeap(n,d);
    while(!q.Empty())
    {
        k = q.Pop().nod;
        viz[k] = 1;
        lst *p = grp.g[k];
        while(p != NULL)
        {
            if(d[p -> nod] > p -> weight && !viz[p -> nod])
            {
                d[p -> nod] = p -> weight;
                pi[p -> nod] = k;
                q.DecreaseValue(p -> nod,d[p -> nod]);
            }
            p = p -> next;
        }
    }
}

void afisare()
{
    int s = 0;
    for(int i = 2;i <= n;i++)
        s += d[i];
    printf("%d\n%d\n",s,n - 1);
    for(int i = 2;i <= n;i++)
        printf("%d %d\n",i,pi[i]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    prim();
    afisare();
    return 0;
}