#include <bits/stdc++.h>
#define pp pair<int, int>
#define ppp pair<int, pair<int, int> >
#define x first
#define y second

using namespace std;

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

const int N_MAX = 200000 + 5;

int n, m, ans;

priority_queue<ppp, vector<ppp>, greater<ppp> > q;
vector<pp> vec[N_MAX];
bitset<N_MAX> luat;
vector<pp> sol;

int main()
{
    fin >> n >> m;
    while(m--){
        int a, b, c;
        fin >> a >> b >> c;
        vec[a].push_back({b,c});
        vec[b].push_back({a,c});
    }

    q.push({0,{0,1}});

    while(!q.empty()){
        int from = q.top().y.x;
        int capat = q.top().y.y;
        int cost = q.top().x;

        q.pop();

        if(!luat[capat]){
            sol.push_back({from, capat});
            ans += cost;


            for(auto v : vec[capat]){
                if(!luat[v.x]){
                    q.push({v.y, {capat, v.x}});
                    //cout << capat << v.x << endl;
                }
            }
        }

        luat[capat] = true;

    }

    fout << ans << "\n";
    fout << sol.size() - 1 << "\n";

    for(int i = 1; i<sol.size(); ++i)
        fout << sol[i].x << " " << sol[i].y << "\n";

    return 0;
}