#include <stdio.h>  
#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 pb push_back  
#define mp make_pair  
#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;  
      
    freopen("apm.in", "r", stdin);  
    freopen("apm.out", "w", stdout);  
      
    scanf("%d %d", &N, &M);  
    for (i = 0; i < M; ++i)  
        scanf("%d %d %d", &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;
         }  
    }  
           
    printf("%d\n%d\n", bst, N-1);  
    for (i = 0; i < M; ++i)
        if (sol[i])
           printf("%d %d\n", E[i].x, E[i].y);
                 
    return 0;  
}