#include <bits/stdc++.h>

using namespace std;

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

const int INF = 999999;

vector <vector <pair <int, int> > > v;
vector <int> Cost(200005, INF);
vector <int> Father(200003, 0);
vector <int> Arb(200003, 0);

int main()
{
    int Sum = 0;
    int n, m, x, y, c;
    fin >> n >> m;
    v.resize(n + 1);
    for (int i=1; i<=m; ++i)
    {
        fin >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }
    priority_queue <pair <int, int> > q;
    q.push(make_pair(0, 1));
    Cost[1] = 0;
    while (!q.empty())
    {
        int Dist = - q.top().first;
        int Node = q.top().second;
        if(Arb[Node] == 1)
        {
            q.pop();
            continue;
        }
        Sum += Dist;
        Arb[Node] = 1;
        q.pop();

        for (int i = 0; i < v[Node].size(); ++i)
        {
            if (v[Node][i].second < Cost[v[Node][i].first] && !Arb[v[Node][i].first])
            {
                Cost[v[Node][i].first] = v[Node][i].second;
                Father[v[Node][i].first] = Node;
                q.push(make_pair(-Cost[v[Node][i].first], v[Node][i].first));
            }
        }
    }

    fout << Sum << "\n" << n - 1 << '\n';
    for (int i = 1; i <= n; ++i)
    {
        if (Father[i])
            fout << i << " " << Father[i] << '\n';
    }
    return 0;
}