#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

typedef pair < int, int > PII;
typedef pair < int, pair < int, int > > PIII;

const int NMAX = 2e5 + 5;

int N, M, X, Y, C, T[NMAX], ans;

vector < PII > G[NMAX];

priority_queue < PIII, vector < PIII >, greater < PIII > > H;

bool Sel[NMAX];

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> X >> Y >> C;

        G[X].push_back({C, Y});
        G[Y].push_back({C, X});
    }

    return;
}

int main()
{
    Read();

    for(auto it : G[1])
        H.push({it.first, {it.second, 1}});

    Sel[1] = true;

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

        int Node = H.top().second.first;
        int F = H.top().second.second;

        ans += H.top().first;

        T[Node] = F;

        Sel[Node] = true;

        H.pop();

        for(auto it : G[Node])
            if(!Sel[it.second])
                H.push({it.first, {it.second, Node}});
    }

    g << ans << '\n' << N - 1 << '\n';

    for(int i = 1; i <= N; ++i)
        if(T[i])
            g << i << ' ' << T[i] << '\n';

    return 0;
}