/*
                                          .::////++ossss+.  `++:``
                                         -md+ohddhhhhhhMM/  oMMMNds+-`
                                  `/dh`  /M:  `::://///mMo `hMm+oydmmNhs/-`
                                `:hNNM/  /M+   -:://///hMh `mMy/////+oydMNd`
                              `/dNmsoMd` :Mm.`.-:://///yMd`.MM+////////oNMy`
                            `/hNms///dM: :MN/--::::////oMm.-MN/////////dMN-
                          `/hNms/////oMd`-NN+::::::////+mNhhMh////////oMMo
                          yMNy////////dMhdNm/:::::://////+oss/////////mMm.
                          /NNs////////oddyo/::::::://////////////////sMM+
                          `+NMs//////////::::::::::://///////////////mMh`
                           `+NMs//////////::::::::::////////////////sMN:
                            `+MNo/////////::::::::::////////////////mMs`
                             `+MNo/////////:::::::::///////////////sMm.
                               oMN+////////:::::::::///////////////NM/
                                oMm+/////////+ooooosssssssssooo+//yMh
                                `oMm+////+osssssssssssssssssssssssNN.
                                 `oMm+/osssssssssssssssssssssssssdM/
                                  `+NmysssssssssssssssssssssssshNMs
                                    -hMmhyssssssssssssssssyhdNNho-`
                                     `-ohmNmmdddddddmmmmmhys+-``
                                        ``.-:://///::-..```
                                           ````..--:://++oosyyhh+`
                             ```    .+osyyhdmmmmmmmmmmddddhyyshMM/
                           -sdmdy. -dMdhyyysooo+++/////::///:::yMm--os+-`
                          .dMMMMm-/mMmyhddd+::::::::::::omNmmdyohMmNMMMNo
                          +MMMMMNmMMMMMMMMMs::::::::::::sMMMMMMMNMMMMMMMm.
                          oMMMMMMMMMMMMMMNd/::::::::::::+mNMMMMMMMMMMMMMM:
                          /NMMMMMMMMNNmdyo/:::::/+++/::::/ohmmNMMMMMMMMMN-
                          `+hmNNdhyso+/::::::++:+ooo/::+::::/+oyhdmNNNNNy`
                            :mMy/:::::::::::/M+::::::::y::::::::://+oNMs`
                          `/NNs:/shhs/::::::+M:::::::::y:::::::/+//::sMm-
                    ``````oNNo:oNMMMMNy:::::+M:::::::::y:::::+hNMMmo::hMh`     ````
                `.:oydddhhMm+:/yyyhmMMMy::::+M:::::::::y::::sNMMMMMMo:/dMs``/oosssso/-`
              `+hNMNNNNNNNm/:::::://+ymN/:::+N:::::::::y:::sNmhso++sy::/mM+sMNNNNNNNNNh-
              +MMNNNNNNNNNd/::::::+sso:o::::+N:::::::::y:::+/+ss+:::::::+NMNNNNNNNNNNNMy
              +MMNNNNNNNNNNs::::::::::+ooo/:/+:::::::::dyyssso:::::::::::oNNNNNNNNNNNNMh
              -MMMNNNNNNNNNmdddhhhyyyNds//:::::::::::::///+sdNmhhhhhhhddddNNNNNNNNNNNNMo
              `dMMMMMMNNNNNNNNNNNNNNMm/::::::::::::::::::::::/mMNNNNNNNNNNNNNNNNNNMMMMN-
               :NMMMMMMMMMMMMMMMMMMMMMmyo+//:::::::::::::://+odMMMMMMMMMMMMMMMMMMMMMMM+`
                +MNNmNMMMMMMMMMMMMMMMMMMMMNNNNmddhhhhhddmNNNMMMMMMMMMMMMMMMMMMMMMMMNd/`
               :mMdh/.-::/+ooosssyyyhhhhhhhhhddddddddddddddddddddhhhyyssooo+/:ydmMMm.
             `oNMNhhy:           ``      ``````````````````````````         `+hhhNMMm/`
            -hMMNmhhhyo.         ``               `              ``        -shhhhmNMMNs`
          `+mMMNNmhhhhhyo-`      ``               .              ``     .:shhhhhhmNNNMMh.
         .yMMNNNNmhhhhhhhhs+-.`  ``               .              `  `-/oyhhhhhhhhmNNNNMMd:
        :dMMNNNNNmhhhhhhhhhhhyso/:-.``            `         ``..-/+oyyhhhhhhhhhhhNNNNNNMMN+
      `+NMMNNNNNNmhhhhhhhhhhhhhhhhyyssso+++//////://///+++osssyyhhhhhhhhhhhhhhhhhNNNNNNMMMN-
     `sMMMMMNNNNNNhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhdNNNNNMMMMMs
     .MMMMMMMMNNNNdhhhhhhhhhhhhhhhhhhhhhhhhhhhdddhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhmNNNMMMMMMN:
     `+NMMMMMMMNNNmhhhhhhhhhhhhhhhhhhhhhhddmmmmmdhhhmmmmmdhhhhhhhhhhhhhhhhhhhhhdNNNMMMMMMm:
       .yNMMMMMMMNNd/syhhhhhhhhhhhhhhhhdmmmmmmmdhhhhdmmmmdhsssssyyhhhhhhhhhhyyomNNMMMMMMh.
         :dMMMMMMMMNs`.+shhhhhhhhhhysssssssyyhhhhhhhmmdysssssssssssyhhhhhhs/.`hNMMMMMMMs`
          `+NMMMMMMMMh.  .:+syhhhhsssssssssssssssshddssssssssssssssshys+:`  `hMMMMMMMN/`
            .sMMMMMMMMN/     `-:+oooosssssssssssssssssssssssooo+//:-.`     -mMMMMMMMM/
              :MMMMMMMMMd:     `    ```....-----------...````      `     `sNMMMMMMMNMd`
             `sMMmMMMMMMMMh/`                                          .oNMMMMMMMNdhMM+
             /MMmyhmMMMMMMMMmo-                  ``                 `:sNMMMMMMMNdhyymMN-
            .mMmyyyyhmNMMMMMMMNdo:`              ``              `:odNMMMMMMMNdhyyyyyNMh`
           `hMMysyyyyyhdNMMMMMMMMNmy+:.`         ``         `.:+hmNMMMMMMMMNdhyyyyssshMMo
           oMMhssssyyyyyyhdNMMMMMMMMMNNmhs+/:---.-----://oyhmNNMMMMMMMMMNmhhyyyyysssssdMN:
          :NMdsssssssyyyyyyhhmNMMMMMMMMMMMMMMNNNNmNNNNNMMMMMMMMMMMMMMMNdhyyyyyysssssssyNMd`
         .mMNmdhyssssssyyyyyyyhdmNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNmhhyyyyyssssssssyyhNMMo
        `yMNyyhdmmhyssssssyyyyyyyhhdmMMMMMMMMMMMMMMMMMMMMMMMMMMMmdhhyyyyyyssssssyyhmmdhyhMN-
        +MMdsssssyhddhyysssssyyyyyyooshmNMMMMMMMMMMMMMMMMMMMNmhsooyyyyysssssyyddmmhyyssssmMd`
       -NMmsssssssssyyhddhyyssssyysooooosydNNMMMMMMMMMMMMNdysooooosysssyyhdmmdhysssssssssyNMo
      `dMNyssssssssssssssyhhdhhyys++++ooooooshmNMMMMMNmhsoooooo++++yhddddhyysssssssssssssshMN-
     `sMMhsssssssssssssssssssyyhhdhysoooooooooooyhddysoooooooosyyhhhhyyssssssssssssssssssssmMd`
     /MMmssssssssssssssssssssssssssyyhhdddddhhhhyyyhyyyhhhhhhhyysssssssssssssssssssssssssssyMMo`
    -NMNysssssssssssssssssssssssssssssssssssyyyhhhhyyyysssssssssssssssssssssssssssssssssssssdMN-
    /sso/////////////////////////////////////////////////////////////////////////////////////ss/
*/



#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, total, root[200005], depth[200005];
vector <int> ans;

struct muchie {
    int a, b, cost;
}v[400005], h[400005];

void mergesort(int st, int dr)
{
    if(st == dr)
        return;
    int med = (st + dr) / 2;
    mergesort(st, med);
    mergesort(med + 1, dr);
    int i = st, j = med + 1, k = st;
    while(i <= med || j <= dr)
    {
        if(j > dr || (i <= med && v[i].cost < v[j].cost))
            h[k++] = v[i++];
        else
            h[k++] = v[j++];
    }
    for(i = st; i <= dr; i++)
        v[i] = h[i];
}

int find_root(int x)
{
    if(root[x] == 0)
        return x;
    return find_root(root[x]);
}

void join(int x, int y)
{
    if(depth[x] > depth[y])
        root[y] = x;
    if(depth[x] < depth[y])
        root[x] = y;
    if(depth[x] == depth[y])
    {
        root[x] = y;
        depth[y]++;
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> v[i].a >> v[i].b >> v[i].cost;
    mergesort(1, m);
    for(int i = 1; i <= m && ((int) ans.size() < n - 1); i++)
    {
        int x, y;
        x = find_root(v[i].a);
        y = find_root(v[i].b);
        if(x == y)
            continue;
        join(x, y);
        total += v[i].cost;
        ans.push_back(i);
    }
    fout << total << '\n' << n - 1 << '\n';
    for(int i = 0; i < (int) ans.size(); i++)
        fout << v[ans[i]].a << ' ' << v[ans[i]].b << '\n';
    return 0;
}