#include <cstdio>
#include <cstdlib>
#include <vector>
#include <utility>
#include <queue>
using namespace std;


#define muchie pair<long,pair<long,long> >
#define nmax 200010
#define pb push_back
#define mp make_pair
#define cost first
#define start second.first
#define end second.second

struct edge
{
       int x,y;
};
priority_queue<muchie, vector<muchie>, greater<muchie> > q;
vector< edge > arbore;
vector< long > colour(nmax);
long n,m,counter=0,sum=0,x,y,c;

void read_input()
{
     scanf("%ld %ld", &n,&m);
     for(int i=0;i<m;i++)
     {
             scanf("%ld %ld %ld", &x,&y,&c);
             //nodes[x].pb(mp(y,c));
             //nodes[y].pb(mp(x,c));
             q.push(mp(c,mp(x,y)));
             q.push(mp(c,mp(y,x)));
     }
}

int culoare()
{
    for(int i=2;i<=n;i++) if(colour[i]!=colour[i-1]) return 1;
    return 0;
}
void Kruskal()
{
     for(int i=1;i<=n;i++) colour[i]=i;
     while(culoare())
     {
                     muchie New=q.top();
                     q.pop();
                     if(colour[New.start]!=colour[New.end])
                     {
                                       edge neww;
                                       neww.x=New.start;
                                       neww.y=New.end;
                                       arbore.push_back(neww);
                                       sum+=New.cost;
                                       long crt_end=colour[New.end];
                                       for(int i=1;i<=n;i++) if(colour[i]==crt_end) colour[i]=colour[New.start];
                     }
     }
     printf("%ld\n", sum);
     printf("%ld\n", arbore.size());
     for(int i=0;i<arbore.size();i++) printf("%ld %ld\n", arbore[i].x,arbore[i].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i;
    read_input();
    Kruskal();
    //scanf("%i", &i);
    return 0;
}