#include <vector>
#include <cstdlib>
#include <fstream>

using namespace std;

const int NMAX = 200011;
const int oo   = 1 << 29;
typedef pair<int, int> pr;

vector<pr> G[NMAX];
int lHeap;
int d[NMAX], H[NMAX], P[NMAX], apm[NMAX];

void DownHeap(int k)
{
    for(int son = k << 1; son <= lHeap; k = son, son <<= 1)
    {
        if(son < lHeap && d[H[son]] > d[H[son + 1]]) ++son;
        if(d[H[k]] <= d[H[son]]) return;
        swap(H[k], H[son]);
        P[H[k]] = k;
        P[H[son]] = son;
    }
}
void UpHeap(int k)
{
    for(int key = d[H[k]], f = k >> 1; k > 1&& key < d[H[f]]; k = f, f >>= 1)
    {
        swap(H[k], H[f]);
        P[H[k]] = k;
        P[H[f]] = f;
    }
}

inline void push(int x)
{
    H[++lHeap] = x;
    P[x] = lHeap;
    UpHeap(lHeap);
}

inline int pop()
{
    int r = H[1];
    P[H[1]] = -1;
    H[1] = H[lHeap--];
    if(!lHeap) return r;
    P[H[1]] = 1;
    DownHeap(1);
    return r;
}

int main()
{
    int N, M, x, y, c, cost;
    ifstream in("apm.in");
    ofstream out("apm.out");

    for(in >> N >> M; M; --M)
    {
        in >> x >> y >> c;
        G[x].push_back(pr(y, c));
        G[y].push_back(pr(x, c));
    }
    fill(d, d + N + 1, oo);
    d[1] = cost = 0;
    for(push(1); lHeap; )
    {
        x = pop();
        cost += d[x];
        for(auto& y : G[x])
        {
            if(-1 == P[y.first]) continue;
            if(d[y.first] > y.second)
            {
                apm[y.first] = x;
                d[y.first] = y.second;
                if(!P[y.first]) push(y.first);
                else UpHeap(P[y.first]);
            }
        }
    }
    out << cost << '\n' << (N - 1) << '\n';
    for(int i = 2; i <= N; ++i) out << i << ' ' << apm[i] << '\n';

    return EXIT_SUCCESS;
}