#include <fstream>
#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<pair<int, int>> apm;
vector<vector<pair<int, int> > > g;
vector<int> d, t;
vector<bool> sel;
priority_queue <Edge> Q;


int main()
{
    is >> n >> m;
    g = vector<vector<pair<int, int>>>(n+1);
    d = vector<int>(n+1, INF);
    sel = vector<bool>(n+1);
    t = vector<int>(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});
    }

    int sum = 0;
    d[1] = 0;
    Q.push({1, 0});
    while(!Q.empty())
    {
        x = Q.top().node;
        sel[x] = true;
        for(const auto & y : g[x])
        {
            if(!sel[y.first])
            {
                if(d[y.first] > y.second)
                {
                    d[y.first] = y.second;
                    t[y.first] = x;
                    Q.push({y.first, d[y.first]});

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

        while(!Q.empty() && sel[Q.top().node])
            Q.pop();

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