#include <fstream>
#include <vector>

using namespace std;

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

typedef pair < int, int > PII;

const int NMAX = 2e5 + 1;
const int Source = 1;
const int INF = 1e9;

int N, M;
vector < PII > G[NMAX];

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

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 >> M;

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

        Add_Edge(x, y, c);
    }

    return;
}

static inline void Initialize (int Node)
{
    for(int i = 1; i <= N; ++i)
        if(i == Node)
            d[i] = 0, t[i] = 0, Sel[i] = true;
        else
            d[i] = INF, t[i] = -1, Sel[i] = false;

    return;
}

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

    return;
}

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

    Expand(X);

    int Total = 0;

    for(int i = 1; i < N; ++i)
    {
        int pos = 0, dMin = INF;

        for(int j = 1; j <= N; ++j)
            if(!Sel[j] && d[j] < dMin)
                dMin = d[j], pos = j;

        Total += dMin;
        Sel[pos] = 1;

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

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

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

    return;
}

int main ()
{
    Read();

    Prim(Source);

    return 0;
}