#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int N = 200010;
int n,m,i,rx,ry,c,x,y,cost,used[N];
priority_queue<tuple<int,int,int>> pq;
vector<pair<int,int>> sol,v[N];
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    used[1]=1;
    for(auto it:v[1])
        pq.push(make_tuple(-it.second,1,it.first));
    while(pq.size())
    {
        tie(c,x,y)=pq.top();
        pq.pop();
        if(used[x]&&used[y])
            continue;
        cost+=-c;
        sol.push_back(make_pair(x,y));
        if(used[y])swap(x,y);
        used[y]=1;
        for(auto it:v[y])
            if(!used[it.first])
                pq.push(make_tuple(-it.second,y,it.first));
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(auto it:sol)
        fout<<it.first<<' '<<it.second<<'\n';
    return 0;
}