#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5 + 5, INF = 2e3;
int mst;
vector <pair <int, int>> g[NMAX], sol;
bitset <NMAX> inMST;


struct edge{
    int first, second, weight;
};

class ComparePQ{
public:
    bool operator()(edge a, edge b){
        return a.weight > b.weight;
    }
};

priority_queue <edge, vector < edge >, ComparePQ> pq;

int main()
{
    int n, m;

    fin >> n >> m;

    for(int i = 1; i <= m; ++i){
        int a, b, c;

        fin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    edge head;
    pq.push({-1, 1, 0});
    while(!pq.empty()){
        head = pq.top();
        pq.pop();

        if(inMST[head.second] == 1)
            continue;

        inMST[head.second] = 1;
        mst += head.weight;
        sol.push_back({head.first, head.second});

        for(auto &it: g[head.second])
            if(inMST[it.first] == 0)
                pq.push({head.second, it.first, it.second});
    }

    fout << mst << '\n' << sol.size()-1 << '\n';

    for(int i = 1; i < sol.size(); ++i)
        fout << sol[i].first << ' ' << sol[i].second << '\n';

    return 0;
}