# include <cstdio>
# include <string.h>
# include <algorithm>

using namespace std;

# define FIN "apm.in"
# define FOUT "apm.out"

struct muchie
{
     int a, b;
     double c;
} *H;

int N, M, i, j, p1, p2;
double cost, X;
int *T;
int *Ind, nc, cif, *Sol, ct;
char (*s)[30], d1[30], d2[30];

    int cmp2(int A, int B)
    {
        return (strcmp(s[A], s[B]) < 0);
    }
    
    int search(int st, int dr, char *p)
    {
        int mij;
        
        while (st <= dr)
        {
              mij = (st + dr) / 2;
              
              if (strcmp(p, s[Ind[mij]]) == 0) return Ind[mij];
              if (strcmp(p, s[Ind[mij]]) > 0) st = mij + 1;
              else dr = mij - 1;
        }
    }
    
    int father(int nod)
    {
        while (T[nod] != nod) nod = T[nod];
        return nod;
    }
    
    int cmp1(muchie A, muchie B)
    {
        return A.c < B.c;
    }

    int main()
    {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);
        
        //scanf("%lf%d", &X, &N);
        scanf("%d", &N);
        Ind = new int[N + 5];
        T = new int [N + 5];
        s = (char (*)[30]) calloc((N + 5), sizeof(char [30]));
        for (i = 1; i <= N; ++i)
        {
            //scanf("%s", s[i]);
            nc = i; cif = 0;
            while (nc != 0) {nc /= 10; ++cif; }
            nc = i;
            //s[i][cif--] = '\n';
            cif--;
            while (nc != 0) {s[i][cif--] = nc % 10 + '0'; nc /= 10;}
            Ind[i] = i;
        }
        
        sort(Ind + 1, Ind + N + 1, cmp2);
        
        scanf("%d", &M);
        H = new muchie[M + 5];
        for (i = 1; i <= M; ++i)
        {
            scanf("%s%s%lf", d1, d2, &H[i].c);
            H[i].a = search(1, N, d1);
            H[i].b = search(1, N, d2);
        }
        
        sort(H + 1, H + M + 1, cmp1);
        Sol = new int[N + 5];
        for (i = 1; i <= N; ++i) T[i] = i;
        for (i = 1; i <= M; ++i)
        {
            p1 = father(H[i].a);
            p2 = father(H[i].b);
            if (p1 != p2)
            {
                   T[p2] = p1;
                   cost += H[i].c;
                   Sol[++ct] = i;
            }
        }
        
        /*if (cost <= X) printf("Need %.1lf miles of cable", cost);
        else printf("Not enough cable");*/
        printf("%.0lf\n%d\n", cost, N - 1);
        for (i = 1; i <= ct; ++i) printf("%d %d\n", H[Sol[i]].a, H[Sol[i]].b);
        
        return 0;
    }