#include <cstdio>

#define MAX 200500
#define INF 100000000

using namespace std;

int n,m;

struct nod
{
    int point;
    int cost;
    nod* urm;
}*point[MAX];

struct solutie
{
    int x, y;
} sol[MAX];

struct minimuri
{
    int from;
    int cost;
} mins[MAX];

int s[MAX];
int minim;


void citire()
{
    freopen("apm.in", "r", stdin);
    scanf("%d %d", &n, &m);
    int x, y, Cost;
    nod * p;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &x, &y, &Cost);
        p = new nod;
        p->point = y;
        p->cost = Cost;
        p->urm = point[x];
        point[x] = p;
        p = new nod;
        p->point = x;
        p->cost = Cost;
        p->urm = point[y];
        point[y] = p;
    }
    fclose(stdin);
}

void afisare()
{
    freopen("apm.out", "w", stdout);
    printf("%d\n", minim);
    printf("%d\n", n - 1);
    for(int i = 1; i < n; i++)
    {
        printf("%d %d\n", sol[i].x, sol[i].y);
    }
    fclose(stdout);
}



int main()
{
    citire();
    int i;
    nod * p;
    for(i = 2; i <= n; i++)
    {
        s[i] = 1;
        mins[i].cost = INF;
        mins[i].from = 0;
        p = point[1];
        while(p && p->point != i)
        {
            p = p->urm;
        }
        if(p)
        {
            mins[i].cost = p->cost;
            mins[i].from = 1;
        }
    }
    int k;
    int min;
    int j;
    for(k = 1; k < n; k++)
    {
        min = INF;
        for(i = 1; i <= n; i++)
        {
            if(s[i])
            {
                p = point[s[i]];
                if(min > mins[i].cost)
                {
                    min = mins[i].cost;
                    j = i;
                }

            }
        }
        sol[k].x = s[j];
        sol[k].y = j;
        s[j] = 0;
        minim += min;
        for(i = 1; i <= n; i++)
        {
            if(s[i])
            {
                p = point[j];
                while(p && p->point!= i)
                {
                    p = p->urm;
                }
                if(p)
                {
                    if(p->cost < mins[i].cost)
                    {
                        mins[i].cost = p->cost;
                        mins[i].from = j;
                        s[i] = j;
                    }
                }
            }
        }
        s[j] = 0;
    }
    afisare();
    return 0;
}