#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Padure
{
private:
    struct Nod
    {
        Nod* urm;
        int rang;
        Nod()
        {
            urm = this;
            rang = 0;
        }
    };
    vector<Nod*> noduri;

    Nod *get_radacina(Nod* n)
    {
        if(n->urm == n)
            return n;
        n->urm = get_radacina(n->urm);
        return n->urm;
    }

public:
    Padure(int n)
    {
        noduri.resize(n);
        for(auto& nod : noduri)
            nod = new Nod();
    }
    ~Padure()
    {
        for_each(noduri.begin(),noduri.end(),[](Nod *n){delete n;});
    }

    bool same_set(int s1, int s2)
    {
        return get_radacina(noduri[s1]) == get_radacina(noduri[s2]);
    }

    void merge_sets(int s1, int s2)
    {
        Nod *rad1 = get_radacina(noduri[s1]);
        Nod *rad2 = get_radacina(noduri[s2]);

        if(rad1->rang == rad2->rang)
        {
            rad1->rang++;
            rad2->urm = rad1;
        }
        else if(rad1->rang > rad2->rang)
            rad2->urm = rad1;
        else
            rad1->urm = rad2;
    }
};

class Graf
{
    struct Muchie
    {
        int n1,n2,cost;
        Muchie(int n1, int n2, int cost):n1{n1},n2{n2},cost{cost}{}
    };
    int N, M;
    vector<Muchie> muchii;
public:
    Graf(char *file)
    {
        freopen(file, "r", stdin);
        scanf("%d %d",&N,&M);
        for(int i=1;i<=M;i++)
        {
            int n1, n2, cost;
            scanf("%d%d%d",&n1,&n2,&cost);
            muchii.push_back(Muchie(n1,n2,cost));
        }


    }

    int kruskal(vector<pair<int, int> >& result)
    {
        sort(muchii.begin(),muchii.end(),[](const Muchie& m1,const Muchie& m2){return m1.cost < m2.cost;});
        int cost_total = 0;
        Padure disjoint_set(N+1);
        for(auto muchie : muchii)
        {
            if(disjoint_set.same_set(muchie.n1, muchie.n2))
                continue;
            disjoint_set.merge_sets(muchie.n1, muchie.n2);
            result.push_back(make_pair(muchie.n1, muchie.n2));
            cost_total+=muchie.cost;
        }
        return cost_total;
    }

};



int main()
{
    Graf g("apm.in");
    freopen("apm.out","w",stdout);
    vector<pair<int, int> > res;
    int cost = g.kruskal(res);

    printf("%d\n%d\n",cost, res.size());
    for(auto m : res)
        printf("%d %d\n",m.first, m.second);

    return 0;
}