#include <fstream>
#include <queue>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,i,x,y,cost,nod,nod2,sum;
vector<pair<int,int>> v[100005],sol;
bool viz[100005];
struct elem
{
    int x,y,cost;
};
class cmp{
    public:
    bool operator() (elem a,elem b)
    {
        return a.cost>b.cost;
    }
};
priority_queue<elem,vector<elem>,cmp> pq;
void dfs(int nod)
{
    viz[nod]=1;
    for(auto x:v[nod])
    {
        int nod2=x.first,cost=x.second;
        if(!viz[nod2])
        {
            pq.push({nod,nod2,cost});
        }
    }
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>cost;
        v[x].push_back({y,cost});
        v[y].push_back({x,cost});
    }
    dfs(1);
    while(!pq.empty())
    {
        int nod=pq.top().x,nod2=pq.top().y,cost=pq.top().cost;
        pq.pop();
        if(viz[nod2]) continue;
        sum+=cost;
        sol.push_back({nod,nod2});
        dfs(nod2);
    }
    cout<<sum<<"\n"<<sol.size()<<"\n";
    for (auto x: sol)
        cout<<x.first<<" "<<x.second<<"\n";
    return 0;
}