#include <iostream>
#include <vector>
#include <tuple>
#define inf 1e9
#include <unordered_map>
#include <fstream>

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

int main()
{
    int N, M, x, y, c, suma = 0;
    //CITIREA SI ADAUGAREA MUCHIILOR
    fin >> N >> M;
    std::vector <std::vector<std::tuple <int, int>>> muchii;
    std::vector <std::tuple <int, int>> muchii_apcm;
    std::tuple <int, int> tuplu;
    muchii.resize(N);
    for(int i = 0; i < M; i++)
    {
        fin >> x >> y >> c;
        tuplu = {y - 1, c};
        muchii[x - 1].push_back(tuplu);
        tuplu = {x - 1, c};
        muchii[y - 1].push_back(tuplu);
    }
    //VECTORII DE TATI SI DISTANTE + MULTIMEA Q
    std::vector <int> d, t;
    std::unordered_map <int, int> noduri;
    for(int i = 0; i < N; i++)
        noduri[i] = 1;
    //incepem prin a avea infinit peste tot
    d.resize(N, inf);
    //nu exista niciun fiu inca
    t.resize(N, 0);
    //pornim cu nodul 0
    d[0] = 0;
    //cat timp mai avem noduri de adaugat in apcm
    while(!noduri.empty())
    {
        //u initial va fi nodul 0 deoarece am pus d[0] = 0;
        int u, minim = inf;
        for(int i = 0; i < N; i++)
            if(d[i] < minim && noduri.find(i) != noduri.end())
                minim = d[i], u = i;


        for(int i = 0; i < muchii[u].size(); i++)
        {
            x = std::get<0>(muchii[u][i]);
            c = std::get<1>(muchii[u][i]);
            if(noduri.find(x) != noduri.end() && c < d[x])
                d[x] = c, t[x] = u;
        }
        noduri.erase(u);
    }
    for(int i = 0; i < N; i++)
        suma += d[i];
    fout << suma << '\n' << N - 1 << '\n';
    for(int i = 1; i < N; i++)
        fout << i + 1<< " " << t[i] + 1 << '\n';
    return 0;
}