#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm> 
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

class Graph
{
    int n;                          //nr de noduri
    int m;                          //nr de muchii
    vector<vector<int> > neighbors; //vector ce contine cate un vector cu vecini pt fiecare nod
    vector<vector<int> > weights; //vector ce contine cate un vector cu costurile pana la vecinii fiecarui nod
    bool oriented;                  // variabiabila pt a verifca daca e orientat
    bool from1;                     // variabila pt a verifica daca nodurile sunt numerotate de la 1
public:
    //constructori:
    Graph(int, bool, bool);
    Graph(int, int, bool, bool);

    void insert_edge(int, int); //functie pt a insera muchii

    void insert_weight(int, int, int); //functie pt a insera costuri
    vector<int> apm(int &); //functie ce returneaza un vector cu parintii fiecarui nod din arborele partial de cost minim al grafului si costul total al muchiilor acestuia(transmis ca parametru)
};

Graph::Graph(int n, bool oriented = false, bool from1 = false)
{
    this->n = n;
    m = 0;
    this->from1 = from1;
    this->oriented = oriented;
    for (int i = 0; i < n; i++)
    {
        vector<int> aux;
        neighbors.push_back(aux);
        weights.push_back(aux);
    }
}
Graph::Graph(int n, int m, bool oriented = false, bool from1 = false)
{
    this->n = n;
    this->m = m;
    this->from1 = from1;
    this->oriented = oriented;
    for (int i = 0; i < n; i++)
    {
        vector<int> aux;
        neighbors.push_back(aux);
        weights.push_back(aux);
    }
}

void Graph::insert_edge(int x, int y)
{
    if (from1)
    {
        neighbors[x - 1].push_back(y - 1);
        if (!oriented)
            neighbors[y - 1].push_back(x - 1);
    }
    else
    {
        neighbors[x].push_back(y);
        if (!oriented)
            neighbors[y].push_back(x);
    }
}


void Graph::insert_weight(int x, int y, int z)
{
    if (from1)
    {
        weights[x - 1].push_back(z);
        if (!oriented)
            weights[y - 1].push_back(z);
    }
    else
    {
        weights[x].push_back(z);
        if (!oriented)
            weights[y].push_back(z);
    }
}

vector<int> Graph::apm(int &total_weight){
    vector<int> keys;
    vector<int> parents;
    vector<bool> visited;
    total_weight = 0;
    for(int i = 0; i < n; i++){
        keys.push_back(1001);
        parents.push_back(-1);
        visited.push_back(false);
    }
    keys[0] = 0;
    
    for(int i = 0; i < n; i++){
        int min_key = 1001;
        int next_node;
        for(int j = 0; j < n; j++){
            if(keys[j] <= min_key && !visited[j]){
                min_key = keys[j];
                next_node = j;
            }
        }
        visited[next_node] = true;
        total_weight += min_key;
        for(int j =0; j < neighbors[next_node].size(); j++){
            if(!visited[ neighbors[next_node][j] ] && (weights[next_node][j] < keys[ neighbors[next_node][j] ])){
                keys[ neighbors[next_node][j] ] = weights[next_node][j];
                parents[ neighbors[next_node][j] ] = next_node;
            }
        }
    }
    return parents;
}



int main()
{
    int n, m, x, y, z;
    fin >> n >> m;
    Graph g(n, m, false, true);
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> z;
        g.insert_edge(x, y);
        g.insert_weight(x, y, z);
    }
    vector<int> aux;
    int total_weight;
    aux = g.apm(total_weight);
    fout<<total_weight<<'\n'<<n-1<<'\n';
    for(int i =0; i < aux.size(); i++){
        if(aux[i] >=0)
            fout<<i+1<<" "<<aux[i]+1<<'\n'; 
    }

    
}