#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

#define v first
#define cost second

using namespace std;

struct cmp{
    bool operator()(const pair<int,pair<int,int> > A,const pair<int,pair<int,int> > B)
    {
        return A.second.cost>B.second.cost;
    }
};

vector<pair<int,int> > lv;
vector<pair<int,int> > ::iterator it;
priority_queue<pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >, cmp> Q;
int n,m,used[200001],ctotal;
void kruskal()
{
    fscanf(f,"%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=n;++i)
        used[i]=i;
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        Q.push(make_pair(a,make_pair(b,c)));
    }
    int va,vb,cst,vrtxes=0;//vector a, vector b, cost
    while(!Q.empty())
    {

        va=Q.top().first;
        vb=Q.top().second.first;
        cst=Q.top().second.cost;
        Q.pop();
        if(used[va]!=used[vb])
        {
             ++vrtxes;
            for(int i=1;i<=n;++i)
                if(used[i]==used[va])used[i]=used[vb];
            ctotal+=cst;
            lv.push_back(make_pair(va,vb));
        }
        if(vrtxes==n-1)return;
    }
}
int main()
{
    kruskal();
    fprintf(g,"%d\n%d\n",ctotal,lv.size());
    for(it=lv.begin();it!=lv.end();++it)
        fprintf(g,"%d %d\n",it->first,it->second);
    return 0;
}