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

using namespace std;

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

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 prim()
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > Q;

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

    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 cost, start, end;

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

        Q.pop();

        if(viz[end] == false)
        {
            viz[end] = true;
            costSol += cost;

            sol.push_back(make_pair(start, end));

            for(int i = 0; i < vecini[end].size(); i++)
            {
                if(viz[vecini[end][i].second] == false)
                {
                    Q.push(make_tuple(vecini[end][i].first, end, vecini[end][i].second));
                }
            }
        }
    }

    printf("%d\n%d\n", costSol, 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();
    prim();


    return 0;
}