#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

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

int *d, *tata, n, m, *viz;
vector<vector<pair<int, int>>> adiacenta;
vector<pair<int, int>> rezultat;

bool Comparatie_PQ(pair<int, int> a, pair<int, int> b)
{
    return a.second > b.second;
}

priority_queue<pair<int,int>, vector<pair<int,int>>, 
    function<bool(pair<int,int>, pair<int,int>)>> mind(Comparatie_PQ);

void Citire();

void IntroduInApm(int);

int main()
{
    Citire();

    d[1] = 0;
    IntroduInApm(1);

    int suma = 0;
    int nrNoduri = 1;
    while (nrNoduri < n)
    {
        int nod = mind.top().first;
        int cost = mind.top().second;
        mind.pop();
        if (viz[nod] == 1)
            continue;
        suma += cost;
        rezultat.push_back({tata[nod], nod});
        IntroduInApm(nod);
        nrNoduri ++;
    }
    
    fout << suma << '\n';
    fout << rezultat.size() << '\n';

    for(auto m : rezultat)
    {
        fout << m.first << " " << m.second << '\n';
    }


    delete[] d;
    delete[] tata;
    delete[] viz;
    return 0;
}

void Citire()
{
    fin >> n >> m;
    d = new int[n + 1];
    tata = new int[n + 1];
    viz = new int[n + 1];
    adiacenta.resize(n + 1);

    for (int i = 1; i <= n ; i ++){
        d[i] = 0x3f3f3f3f; // initializam d cu infinit
    }
    for (int i = 1; i <= m; i ++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        adiacenta[x].push_back({y, c});
        adiacenta[y].push_back({x, c});
    }
}

void IntroduInApm(int x)
{
    viz[x] = 1;
    for (int i = 0; i < adiacenta[x].size(); i ++)
    {
        
        int nod = adiacenta[x][i].first;
        int cost = adiacenta[x][i].second;
        
        if (viz[nod] == 1)
            continue;
        
        d[nod] = min(d[nod], cost);
        
        if (d[nod] == cost){
            tata[nod] = x;
            mind.push({nod, cost});
        }
    }
}