#include <cstdio>
#include <algorithm>

using namespace std;

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

int comp[200010];
int sol[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--;
    }

    for(int i = 0; i < n; i++)
        comp[i] = i;
}

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 solve()
{
    citire();
    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(comp[u[j].x]!= comp[u[j].y])
            {
                aux = comp[u[j].y];
                for(k = 0; k < n; k++)
                    if(comp[k] == aux)
                        comp[k] = comp[u[j].x];
                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;
}