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

FILE *f = freopen("apm.in", "r", stdin);
FILE *g = freopen("apm.out", "w", stdout);

const int N_MAX = 200001;

struct vecin{
    int capat;
    int cost;

    vecin (int &a, int &b)
    {
        this -> capat= a;
        this -> cost= b;
    }
};

struct muchie{
    int capat1;
    int capat2;
    int cost;

    muchie(int &a, int &b, int &c)
    {
        this -> capat1 = a;
        this -> capat2= b;
        this -> cost= c;
    }

    const bool operator <(const muchie &other) const
    {
        return (this ->cost > other.cost);
    }
};

int n, m, sol;
int rez[N_MAX];
vector <vecin> G[N_MAX];
vector <vecin> solutie;
priority_queue <muchie> candidati;

int main()
{
    scanf("%d %d", &n, &m);

    for (int i=1; i<=m; i++)
    {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);

        G[x].push_back(vecin(y,c));
        G[y].push_back(vecin(x,c));
    }
    rez[1] = true;
    sol = 1;

    for (vecin i : G[1])
        candidati.push(muchie (sol, i.capat, i.cost));

    sol = 0;

    while (!candidati.empty())
    {
        muchie v = candidati.top();
        candidati.pop();

        if (!(rez[v.capat1] && rez[v.capat2]))
        {
            int nod_nou;
            if (!rez[v.capat1])
                nod_nou = v.capat1;
            else
                nod_nou = v.capat2;

            rez[nod_nou] = true;
            sol += v.cost;

            solutie.push_back(vecin(v.capat1, v.capat2));

            for (vecin i :G[nod_nou])
            {
                if (!rez[i.capat])
                {
                    candidati.push(muchie(nod_nou, i.capat, i.cost));
                }
            }
        }
    }

    printf("%d\n", sol);
    printf("%u\n", solutie.size());
    for (int i=0; i<solutie.size(); i++)
    {
        printf("%d %d\n", solutie[i].capat, solutie[i].cost);
    }
    return 0;
}