#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

vector<int> d(200001, 1e9), viz(200001, 0), p(200001, -1);
vector <pair<int, int>> L[2000001], apcm;
priority_queue<pair<int, int>> pq; 

int main()
{
    int n, m;
    fin >> n >> m;

    for(int i = 0; i < m; i ++)
    {
        int x, y, w;

        fin >> x >> y >> w;
        L[x].push_back({y, w});
        L[y].push_back({x, w});
    }

    d[1] = 0;

    pq.push({-d[1], 1});

    int cost = 0;

    while(pq.size() > 0)
    {
        int w = - pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if(viz[node] == 0)
        {
            viz[node] = 1;
            cost += w;

            if(node != 1)
                apcm.push_back({node, p[node]});

            for(auto v: L[node])
            {
                if(d[v.first] > v.second)
                {
                    d[v.first] = v.second;
                    pq.push({-d[v.first], v.first});
                    p[v.first] = node;
                }
            }
        }  
    }

    fout << cost << '\n' << apcm.size() << '\n';

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

    return 0;
}