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

using namespace std;

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

typedef pair < int, int > PII;

const int NMAX = 2e5 + 1;
const int ROOT = 1;

const int INF = 1e9;

int N;

vector < PII > G[NMAX];

int d[NMAX];
bool Sel[NMAX];
int t[NMAX];

auto cmp = [] (PII A, PII B)
{
    if(!(A.first < B.first))
        return 1;

    return 0;
};
priority_queue < PII, vector < PII >, decltype(cmp) > H(cmp);

static inline void Add_Edge (int x, int y, int c)
{
    G[x].push_back({c, y});
    G[y].push_back({c, x});

    return;
}

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

    f >> N;

    int E = 0;
    f >> E;

    for(int i = 1; i <= E; ++i)
    {
        int x = 0, y = 0, c = 0;
        f >> x >> y >> c;

        Add_Edge(x, y, c);
    }

    return;
}

static inline void Initialize (int Source)
{
    for(int i = 1; i <= N; ++i)
        d[i] = INF, Sel[i] = false;

    d[Source] = 0, Sel[Source] = true;

    return;
}

static inline void Expand (int Source)
{
    for(auto it : G[Source])
        if(it.first < d[it.second])
            d[it.second] = it.first, t[it.second] = Source, H.push(it);

    return;
}

static inline void Prim (int Source)
{
    Initialize(Source);

    Expand(Source);

    int ans = 0;

    while(!H.empty())
    {
        while(!H.empty() && Sel[H.top().second])
            H.pop();

        if(H.empty())
            break;

        int Node = H.top().second;
        ans += H.top().first;

        Sel[Node] = true, H.pop();

        for(auto it : G[Node])
            if(!Sel[it.second] && it.first < d[it.second])
                d[it.second] = it.first, t[it.second] = Node, H.push(it);
    }

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

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

    return;
}

int main()
{
    Read();

    Prim(ROOT);

    return 0;
}