#include <iostream>  
#include <fstream>
#include <algorithm>  
#include <vector>  
   
using namespace std;  
   
#define PII pair< pair<int, int>, int >  
#define x first.first  
#define y first.second  
#define c second   
#define MMax 400004  
#define NMax 200002  
   
int N, M, up[NMax], rang[NMax], bst;  
char sol[MMax];
PII E[MMax];  
   
bool cmp(const PII &a, const PII &b)  
{ return a.c < b.c; }  
   
void uneste(int xx, int yy)  
{  
     if (rang[xx] < rang[yy])  
        up[xx] = yy;  
     else 
     {  
         up[yy] = xx;  
         rang[xx] += (rang[xx] == rang[yy]);  
     }  
}  
   
int find_multime(int xx)  
{  
    if (xx != up[xx])  
       up[xx] = find_multime(up[xx]);  
    return up[xx];  
}  
   
int main()  
{  
    int i, u, v;  
       
    ifstream f("apm.in");
    ofstream g("apm.out"); 
       
    f>>N>>M;   
    for (i = 0; i < M; ++i) 
        f>>E[i].x>>E[i].y>>E[i].c; 
    sort(E, E+M, cmp);  
       
    for (i = 1; i <= N; ++i)  
        up[i] = i, rang[i] = 1;  
       
    for (i = 0; i < M; ++i)  
    {  
        u = find_multime(E[i].x);  
        v = find_multime(E[i].y);  
        if (u != v)  
        {  
           uneste(u, v);  
           bst += E[i].c;  
           sol[i] = 1;
         }  
    }  
          
    g<<bst<<"\n"<<N-1<<"\n";   
    for (i = 0; i < M; ++i)
        if (sol[i])
           g<<E[i].x<<" "<<E[i].y<<"\n";
           
    f.close();
    g.close();
              
    return 0;  
}