#include <bits/stdc++.h>
#define nod pair <int, pair <int,int>>
#define edge pair <int,int>
#define mp make_pair
#define pb push_back

using namespace std;

vector < nod > G[200005];
priority_queue < nod , vector<nod >, greater<nod> > H;
vector <edge> Sol;
nod Min;

int N, M, x, y, c;
long long cost;
bool Sel[200005];
ifstream f ("apm.in");
ofstream g ("apm.out");

int main()
{
    f >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        f >> x >> y >> c;
        G[x].pb(mp(c, mp(x, y)));
        G[y].pb(mp(c, mp(y, x)));
    }

    for (int i = 0; i < G[1].size(); ++i)
    {
        H.push(G[1][i]);
    }

    Sel[1] = true;

    for (int i = 1; i < N; ++i)
    {
        while (Sel[H.top().second.second])
        {
            H.pop();
        }

        Min = H.top(); x = Min. second.first; y = Min.second.second;
        Sol.pb(mp(x, y));
        Sel[y] = true;
        cost = cost + Min.first;
        for ( auto it : G[y])
        {
            if (!Sel[it.second.second])
            {
                H.push(it);
            }
        }
    }

    g << cost << '\n';
    g << Sol.size() << '\n';

    for ( auto it : Sol)
    {
        g << it.first << " " << it.second << '\n';
    }
    return 0;
}