#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int MMAX = 400005;
const int NMAX = 200005;
int n,m,i,j,Father[NMAX],X,Y,C,sum;
struct muchie{int x,y,c;} M[MMAX];
bool cmp(muchie a,muchie b) {return a.c<b.c;}
vector<int> Set[NMAX];
vector<pair<int,int> > Sol;
void Read()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++) scanf("%d%d%d",&M[i].x,&M[i].y,&M[i].c);
}
void Unite(int where,int from)
{
    for(vector<int>::iterator it=Set[from].begin();it!=Set[from].end();it++)
    {
        Father[*it]=where;
        Set[where].push_back(*it);
    }
    Set[from].clear();
}
void Kruskal()
{
    sort(M+1,M+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        Father[i]=i;
        Set[i].push_back(i);
    }
    for(i=1;i<=m;i++)
    {
        X=M[i].x; Y=M[i].y; C=M[i].c;
        if(Father[X]!=Father[Y])
        {
            sum+=C;
            if(Set[Father[X]].size()<Set[Father[Y]].size()) Unite(Father[Y],Father[X]);
            else Unite(Father[X],Father[Y]);
            Sol.push_back(make_pair(X,Y));
        }
    }
}
void Print()
{
    printf("%d\n%d\n",sum,Sol.size());
    for(vector<pair<int,int> >::iterator it=Sol.begin();it!=Sol.end();it++) printf("%d %d\n",it->first,it->second);
}
int main()
{
    Read();
    Kruskal();
    Print();
    return 0;
}