#include <bits/stdc++.h>
#define PII pair < int , int >

using namespace std;

int pozr;
char buffer[1010];
FILE *fi, *fo;
             
char getch(){
    if( pozr == 1010 ){
        fread( buffer, 1010, 1, fi  );
        pozr = 0;
    }
    return buffer[ pozr++ ];
}
             
int scano(){
    int nr = 0, sign = 1;
    char ch = getch();
    while( isdigit(ch) == 0 && ch != '-'){
        ch = getch();
    }

    if (ch == '-'){
        sign = -1;
        ch = getch();
    }

    while( isdigit(ch) != 0 ){
        nr = nr * 10 + ch - '0';
        ch = getch();
    }

    return nr * sign;
}

int n, m, apm, dad[200005], dist[200005];
vector < PII > V[200005];
set < PII > S;
bitset < 200005 > B;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    fi = fopen("apm.in", "r");
    fo = fopen("apm.out", "w");
    n = scano(); m = scano();

    for (int i = 1; i <= n; i++) dist[i] = 2e9;

    for (int i = 1, x, y, z; i <= m; i++){
        x = scano();
        y = scano();
        z = scano();

        V[x].push_back({y, z});
        V[y].push_back({x, z});
    }

    S.insert({0, 1});
    dist[1] = 0;

    while (S.size()){
        apm += S.begin()->first;

        int node = S.begin()->second;
        S.erase(S.begin());
        B[node] = 1;

        for (auto it : V[node]){
            int vertex = it.first;
            int weight = it.second;

            if (!B[vertex] && weight < dist[vertex]){
                if (dist[vertex] != 2e9)
                    S.erase(S.find({dist[vertex], vertex}));

                dist[vertex] = weight;
                dad[vertex] = node;
                S.insert({dist[vertex], vertex});
            }
        } 
    }

    fprintf(fo, "%d\n%d\n", apm, n - 1);
    for (int i = 1; i <= n; i++){
        if (dad[i] != 0)
            fprintf(fo, "%d %d\n", dad[i], i);
    }

    return 0;
}