/*Kruskal*/

    # include <cstdio>
    # include <algorithm>
    # include <vector>
    using namespace std;

    #define NMAX 400001

    int N,M,rasp;

    int A[NMAX],POZ[NMAX];
    int M1[NMAX],M2[NMAX],C[NMAX];

    vector<int>SOL;

    int FindSet(int x){
        if( A[x] == x ) return x;
        A[x] = FindSet(A[x]);
        return A[x];
    }

    void Union(int u, int v){
        A[FindSet(u)] = FindSet(v);
    }

    void MakeSet(int k){
        A[k] = k;
    }

    bool cmp(int u, int v){
        return (C[u] < C[v]);
    }

    void read(){
        scanf("%d%d", &N, &M);
        for(int i=1; i<=M; i++){
            scanf("%d%d%d", &M1[i], &M2[i], &C[i]);
            POZ[i] = i;
        }
    }

    int main()
    {
        freopen("apm.in", "rt", stdin);
        freopen("apm.out", "wt", stdout);

        read();

        for(int i=1; i<=N; i++) MakeSet(i);
        sort(POZ + 1, POZ + M + 1, cmp);

        for(int i=1; i<=M; i++){
            if( FindSet(M1[POZ[i]]) != FindSet(M2[POZ[i]]) ){
                rasp += C[POZ[i]];
                Union( M1[POZ[i]], M2[POZ[i]] );
                SOL.push_back(POZ[i]);
            }
        }
        printf("%d\n%d\n",rasp,N-1);
        for(int i=0; i < N-1; i++)
            printf("%d %d\n", M1[SOL[i]], M2[SOL[i]]);
        return 0;
    }