#include <bits/stdc++.h>
#define Roc ios_base::sync_with_stdio(false), cin.tie(NULL)
#define ll long long
#define NMAX 200009
#define pi pair<ll,ll>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

typedef pair<ll, pi> mch;
vector <pi> G[NMAX];
vector <pi> sol;
ll n, m, x, y, c,cat, t[NMAX],viz[NMAX];
priority_queue<mch, vector<mch>, greater<mch> > Q;
int main()
{
    Roc;
    f >> n >> m;
    while(f >> x >> y >> c)
    {
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
    for(auto it : G[1])
    {
        ///g << it.first << ' ' << it.second << '\n';
        Q.push({it.second, {1, it.first} });
    }
    viz[1] = 1;
    while(!Q.empty())
    {
        mch act = Q.top();
        Q.pop();
        if(!viz[act.second.second])
        {
            cat += act.first;
            ///t[act.second.second] = act.second.first;
            sol.push_back({act.second.first, act.second.second});
            viz[ act.second.second ] = 1;
            for(auto it : G[act.second.second])
                if(!viz[it.first])
                    Q.push({it.second, {act.second.second, it.first} });
        }
    }
    g << cat << '\n';
    g << sol.size() << '\n';
    for(auto it : sol)
        g << it.first << ' ' << it.second << '\n';
    /*
    for(ll i = 1; i <= n; ++i)
        g << t[i] << ' ';
    */
    f.close();
    g.close();
    return 0;
}