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

using namespace std;

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

int n,m;
int cost;
int parent[200005];
int card[200005];

vector<pii >ans;
priority_queue<piii,vector<piii >,greater<piii > >pq;

int find_parent(int pos)
{
    if (parent[pos]!=pos)
    {
        parent[pos]=find_parent(parent[pos]);
        return parent[pos];
    }
    return pos;
}

void reuniune(int x,int y)
{
    x=find_parent(x);
    y=find_parent(y);
    if (card[x]<card[y])
        swap(x,y);
    parent[y]=x;
    card[x]+=card[y];
}

void compute_answer()
{
    while(ans.size()!=n-1)
    {
        int c=pq.top().first;
        int x=pq.top().second.first;
        int y=pq.top().second.second;
        pq.pop();
        if(find_parent(x)==find_parent(y))
            continue;
        ans.push_back({x,y});
        cost+=c;
        reuniune(x,y);
    }
}
int main()
{
    fin>>n>>m;
    int c,x,y;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        pq.push({c,{x,y}});
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        card[i]=1;
    }
    compute_answer();
    fout<<cost<<"\n";
    fout<<n-1<<"\n";
    for(int i=0;i<ans.size();i++)
        fout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}