#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

ifstream is("apm.in");
ofstream os("apm.out");

struct Edge{
    int node, cost;
    bool operator < (const Edge& other) const
    {
        return cost > other.cost;
    }

};

int n, m;
vector<vector<pair<int, int>>> g;
vector<pair<int, int>> apm;
vector<int> d, t;
vector<bool> s;
priority_queue <Edge> heap;
int sum;

void Read();
void Write();
void Solve(int k);

int main()
{
    Read();
    Solve(1);
    Write();
    is.close();
    os.close();
    return 0;
}


void Read()
{
    is >> n >> m;
    g = vector<vector<pair<int, int>>>(n+1);
    t = vector<int>(n+1);
    d = vector<int>(n+1, INF);
    s = vector<bool>(n+1);
    int x, y, z;
    for(int i = 1; i <= m; ++i)
    {
        is >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
}

void Write()
{

    os << sum << '\n';
    os << n - 1 << '\n';
    for(int i = 1; i < n; ++i)
    {
            os << apm[i].first << ' ' << apm[i].second << '\n';
    }

}

void Solve(int k)
{
    int x, w;
    d[k] = 0;

    heap.push({k, 0});
    while(!heap.empty())
    {
        k = heap.top().node;
        s[k] = true;
        for(const auto& y : g[k])
        {
            if(!s[y.first])
            {
                if(d[y.first] > y.second)
                {
                    d[y.first] = y.second;
                    t[y.first] = k;
                    heap.push({y.first, d[y.first]});
                }
            }
        }

        apm.push_back({t[k], k});
        sum += d[k];

        while(!heap.empty() && s[heap.top().node])
            heap.pop();
    }
}