#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>

using namespace std;

FILE *fin  = fopen("apm.in", "r"), *fout = fopen("apm.out", "w");

#define MAX_N 200000

struct elem  {
    int x, y, c;
};

struct comparator  {
bool operator () (elem a, elem b)  {
    return a.c > b.c;
}
};

vector <elem> v[MAX_N + 1];
int lung[MAX_N + 1];
bool inapm[MAX_N + 1];
priority_queue <elem, vector<elem>, comparator> pq;
vector <elem> sol;

#define inf 2000000000

int main()  {
    int n, m;
    fscanf(fin, "%d%d", &n, &m);
    for(int i = 0;i < m;i++)  {
        int x, y, c;
        fscanf(fin, "%d%d%d", &x, &y, &c);
        v[x].push_back({x, y, c});
        v[y].push_back({y, x, c});
    }

    for(int i = 2;i <= n;i++)
        lung[i] = inf;
    lung[1] = 0;

    int costarb = 0;
    pq.push({0, 1, 0});

    while(!pq.empty())  {
        elem e = pq.top();
        pq.pop();
        int nod = e.y;
        if(lung[nod] < e.c)
            continue;
        inapm[nod] = 1;
        costarb += e.c;
        sol.push_back(e);

        for(unsigned int k = 0;k < v[nod].size();k++)  {
            int next = v[nod][k].y, cost = v[nod][k].c;
            if(inapm[next] || lung[next] <= cost)
                continue;

            lung[next] = cost;
            pq.push({nod, next, cost});
        }
    }

    fprintf(fout, "%d\n%d\n", costarb, sol.size() - 1);
    for(unsigned int k = 1;k < sol.size();k++)
        fprintf(fout, "%d %d\n", sol[k].x, sol[k].y);
    fclose(fin), fclose(fout);
    return 0;
}