#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

using PII = pair < int, int >;

struct str
{
    int a;
    int b;
    int cost;
};

const int NMAX = 2e5 + 3;
const int MMAX = 4e5 + 3;

int N, M;

str edges[MMAX];

vector < PII > mst;

static inline void myswap (int &a, int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

    return;
}

class DSU
{
    int Size[NMAX], sef[NMAX];
private:
    inline int Find (int x)
    {
        if(x == sef[x])
            return x;

        int a = Find(sef[x]);
        sef[x] = a;
        return a;
    }

public:

    inline void Init (int n)
    {
        for(int i = 1; i <= n; ++i)
            sef[i] = i, Size[i] = 1;
    }

    inline void Update (int a, int b)
    {
        a = Find(a);
        b = Find(b);

        if(a == b)
            return;

        if(Size[a] > Size[b])
            myswap(a, b);

        sef[a] = b;
        Size[b] += Size[a];
        Size[a] = 0;

        return;
    }

    inline bool Query (int a, int b)
    {
        return (Find(a) == Find(b));
    }
}dsu;

static inline bool cmp (str a, str b)
{
    return (a.cost < b.cost);
}

static inline void Read ()
{
    fin >> N >> M;
    for(int i = 1; i <= M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        edges[i] = {x, y, c};
    }

    sort(edges + 1, edges + M + 1, cmp);

    return;
}

static inline void Solve ()
{
    int ans = 0;
    dsu.Init(N);
    for(int i = 1; i <= M; ++i) {
        if(dsu.Query(edges[i].a, edges[i].b))
            continue;
        dsu.Update(edges[i].a, edges[i].b);
        mst.push_back({edges[i].a, edges[i].b});
        ans += edges[i].cost;
    }

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

    for(auto it: mst)
        fout << it.first << ' ' << it.second << '\n';

    return;
}

int main()
{
    Read();
    Solve();
    return 0;
}