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

using namespace std;

const int N_MAX = 200000 + 5;

vector<pii> vec[N_MAX], sol;
priority_queue<piii, vector<piii>, greater<piii> > q;


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

bitset<N_MAX> used;

int n, m, ans;

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 to = q.top().y.y;
        int cost = q.top().x;

        q.pop();

        if(!used[to]){
            ans += cost;
            sol.push_back({from, to});
            for(auto v : vec[to])
                if(!used[v.x])
                    q.push({v.y, {to, v.x}});

        }

        used[to] = 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;
}