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

using namespace std;

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

int d[200002], viz[200002], t[200002];

int n, m, a, b, c;

const int INF = 2000;

vector<pair<int, int> > v[200002];

vector<pair<int, int> > e;

struct compP {

    bool operator() (int x, int y) {

        return d[x] > d[y];

    }

};

priority_queue<int, vector<int>, compP> q;

int prim(int start) {

    int sum = 0;

    for (int i=1; i<=n; i++) {
        d[i] = INF;
    }

    d[start] = 0;
    q.push(start);
    viz[start] = 1;

    t[start] = 0;

    while (!q.empty()) {

        int x = q.top();
        q.pop();

        if (t[x] != 0) {
            e.push_back(make_pair(t[x], x));
        }

        sum += d[x];

        for (int i=0; i<v[x].size(); i++) {

            int vecin = v[x][i].first;
            int cost = v[x][i].second;

            if (d[vecin] > cost) {
                d[vecin] = cost;

                t[vecin] = x;

                if (!viz[vecin]) {
                    q.push(vecin);
                    viz[vecin] = 1;
                }

            }

        }



    }

    return sum;

}

int main()
{

    fin>>n>>m;

    for (int i=1; i<=m; i++) {

        fin>>a>>b>>c;

        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));

    }

    fout<<prim(1)<<"\n";
    fout<<e.size()<<"\n";

    for (int i=0; i<e.size(); i++) {
        fout<<e[i].first<<" "<<e[i].second<<"\n";
    }

    return 0;
}