#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
using pi = pair<int,int>;
using ppi = pair<int,pi>;
int n,m,a,b,c,cost,ans;
vector<pi>ans_v;

vector<vector<pi>>sirad;
vector<bool> viz;

void Prim()
{
    priority_queue<ppi,vector<ppi>,greater<ppi>>q;
    q.push({0,{0,1}});

    while(!q.empty())
    {
        int cst = q.top().first,
        p = q.top().second.first,
        nod = q.top().second.second;
        q.pop();

        if(viz[nod]) continue;

        viz[nod] = true;
        cost += cst;
        ans ++;
        ans_v.push_back({p,nod});

        for(auto i : sirad[nod])
        {
            int y = i.first,
            w = i.second;
            if(!viz[y])
                q.push({w,{nod,y}});
        }
    }
}
int main()
{
    cin>>n>>m;
    sirad = vector<vector<pi>>(n+1);
    viz = vector<bool>(n+1);
    while(m--)
    {
        cin>>a>>b>>c;
        sirad[a].push_back({b,c});
        sirad[b].push_back({a,c});
    }

    Prim();

    sort(ans_v.begin(),ans_v.end());
    cout<<cost<<'\n'<<ans-1<<'\n';
    for(int i = 1; i < ans_v.size(); ++i)
        cout<<ans_v[i].first<<' '<<ans_v[i].second<<'\n';
    return 0;
}