#include <cstdio>
#include <algorithm>

using namespace std;

struct muchie
{
    int x, y;
    int cost;
}u[400010];

int par[200010];
int sol[200010];
int h[200010];
int n, m, nsol = 0;

bool cmp(muchie a, muchie b)
{
    if(a.cost < b.cost)
        return true;
    return false;
}

void citire()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u[i].x, &u[i].y, &u[i].cost);
        u[i].x--;
        u[i].y--;
    }
}

void debug()
{
    for(int i = 0; i < m; i++)
        printf("%d\n", u[i].cost);
}

void afisare(int costmin)
{
    printf("%d\n%d\n", costmin, n-1);
    for(int i = 0; i < n-1; i++)
        printf("%d %d\n", u[sol[i]].x + 1, u[sol[i]].y + 1);
}

void setare()
{
    for(int i = 0; i <= n; i++)
        par[i] = -1;
}

int getroot(int x)
{
    if(par[x] == -1)
        return x;
    par[x] = getroot(par[x]);
    h[x] = h[par[x]] + 1;
    return par[x];
}

bool comun(int x, int y)
{
    if(getroot(x) == getroot(y))
        return true;
    return false;
}

void reuniune(int x, int y)
{
    int rx, ry;
    rx = getroot(x);
    ry = getroot(y);
    if(rx == ry)
        return;
    if(h[rx] < h[ry])
        swap(rx, ry);
    par[ry] = rx;
    h[rx] ++;
}

void solve()
{
    citire();
    setare();
    sort(u, u + m, cmp);
    //debug();
    int i, j = 0, k, aux, costmin = 0;
    for(i = 0; i < n-1; i++)
    {
        for(;j < m; j++)
            if(!comun(u[j].x, u[j].y))
            {
                reuniune(u[j].x, u[j].y);
                costmin += u[j].cost;
                sol[nsol++] = j;
                j++;
                break;
            }
    }
    afisare(costmin);
}

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