//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int Max=200005;
const int Mmax=400005;
int n,m,s,tata[Max],grad[Max];
vector <pair <int,int> >muchii;
struct muchie
{
    int x,y,cost;
}muc[Mmax];
bool compara(muchie e1,muchie e2)
{
    return e1.cost<e2.cost;
}
void citire()
{
   in>>n>>m;
   for(int i=1;i<=m;i++)
   {
       int x,y,c; in>>x>>y>>c; muc[i]={x,y,c};
   }

}
int find(int &x,int &y)
{
    while(x!=tata[x] || y!=tata[y])
    {
        x=tata[x]; y=tata[y];
    }
    if(x==y)
        return 1;
    return 0;
}
void uneste(int x,int y)
{
    if(grad[x]<grad[y])
        tata[x]=y;
    else
        tata[y]=x;
    if(grad[x]==grad[y])
        grad[x]++;
}
void Kruskal()
{
  sort(muc+1,muc+m+1,compara);
  for(int i=1;i<=n;i++)
    tata[i]=i;
    int p=0;
    for(int i=1;i<=n-1;i++)
    {
        p++;
        int x=muc[p].x;
        int y=muc[p].y;
       while(find(x,y))
       {
           p++;
           x=muc[p].x;
           y=muc[p].y;
       }
       uneste(x,y);
       s=s+muc[p].cost;
       muchii.push_back({muc[p].x,muc[p].y});

    }
}
int main()
{
    citire();
    Kruskal();
    out<<s<<"\n";
    out<<n-1<<"\n";
    for(int j=0;j<muchii.size();j++)
    {
        out<<muchii[j].first<<" "<<muchii[j].second<<"\n";
    }
    return 0;
}