#include <bits/stdc++.h>

using namespace std;

int PONDERI[100][100];

int NODURI, MUCHII;
vector <bool> ADAUGAT(100000);
vector <int>  DISTANTA(100000);
vector <int>  PARINTE(100000);
vector <pair <int, int> > ADJACENT[200010];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int > > > Q;

void addEdge( int u, int v, int cost){
    ADJACENT[u].push_back(make_pair(v, cost));
    ADJACENT[v].push_back(make_pair(u, cost));
}

void algPrim(int start){
    Q.push(make_pair(0, start));

    DISTANTA[start] = 0;
    while (!Q.empty()){
        int cr = Q.top().second;
        Q.pop();
        ADAUGAT[cr] = true;
        
        for(auto it: ADJACENT[cr]){
            int nextNode = it.first;
            int dist = it.second;

            if(!ADAUGAT[nextNode] && dist < DISTANTA[nextNode]){
                PARINTE[nextNode] = cr;
                DISTANTA[nextNode] = dist;
                
                Q.push(make_pair(DISTANTA[nextNode], nextNode));
            }
        }
    }
}

int main()
{
    ifstream fin("apm.in");
    int noduri, muchii;

    fin >> noduri >> muchii;
    NODURI = noduri;
    
    for(int i = 1; i <= muchii; i++){
        int x, y, cost;
        fin >> x >> y >> cost;
        addEdge(x, y, cost);
    }

    for(int i = 1; i <= noduri; i++){
        ADAUGAT[i] = false;
        DISTANTA[i] = 1e9;
        PARINTE[i] = -1;
    }

    int sum = 0;
    algPrim(1);

    int start = 1;
    for(int i = 1; i <= noduri; i++)
        sum += DISTANTA[i];

    ofstream fout("apm.out");
    fout << sum << endl;
    fout << noduri - 1 << endl;

    for(int i = 1; i <= noduri; i++)
        cout << PARINTE[i] << " ";

    for(int i = 1; i <= noduri; i++){
        if(PARINTE[i] != -1){
            fout << PARINTE[i] << " " << i << "\n";
        }
    }



    return 0;
}