#include <cstdio>
#include <vector>
#include <tuple>
#include <bitset>
#include <queue>

using namespace std;

vector<pair<int, int> > vecini[200005];
bitset<200005> viz;
vector<pair<int, int> > sol;
int n, m;

void citire()
{
    scanf("%d %d", &n, &m);

    int tmp1, tmp2, tmp3;

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &tmp1, &tmp2, &tmp3);

        vecini[tmp1].push_back(make_pair(tmp3, tmp2));
        vecini[tmp2].push_back(make_pair(tmp3, tmp1));
    }
}

void arboreCostMinim()
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > Q;

    int l = vecini[1].size();

    int costTotal = 0;

    tuple<int, int, int> x;

    for(int i = 0; i < l; i++)
    {
        Q.push(make_tuple(vecini[1][i].first, 1, vecini[1][i].second));
    }

    viz[1] = true;

    while(!Q.empty())
    {
        int start, destin, cost;

        cost = get<0>(Q.top());
        start = get<1>(Q.top());
        destin = get<2>(Q.top());

        Q.pop();

        if(viz[destin] == 0)
        {
            sol.push_back(make_pair(start, destin));

            viz[destin] = true;
            costTotal += cost;

            for(int i = 0; i < vecini[destin].size(); i++)
            {
                if(viz[vecini[destin][i].second] == true)
                {
                    continue;
                }
                int nr1, nr2, nr3;
                nr1 = vecini[destin][i].first;
                nr3 = vecini[destin][i].second;

                Q.push(make_tuple(nr1, destin, nr3));
            }
        }
    }

    printf("%d\n%d\n", costTotal, n - 1);

    for(int i = 0; i < sol.size(); i++)
    {
        printf("%d %d\n", sol[i].first, sol[i].second);
    }
}

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

    citire();
    arboreCostMinim();

    return 0;
}