#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
const int nmax=2e5, mmax=4e5;
int n, m, cmin;
int tata[nmax+5];
vector <pair <int, int> > sol;

struct muchie
{
    int x, y, c;
} G[mmax+5];


int cmp(muchie a, muchie b)
{
    return a.c<b.c;
}

int find_set(int x)
{
    if(x==tata[x])
        return x;
    tata[x]=find_set(tata[x]);
    return tata[x];
}

int main()
{
    fi>>n>>m;
    for(int i=1; i<=m; i++)
        fi>>G[i].x>>G[i].y>>G[i].c;

    sort(G+1, G+m+1, cmp);

    for(int i=1; i<=n; i++)
        tata[i]=i;

    for(int i=1; i<=m; i++)
    {
        int rx=find_set(G[i].x), ry=find_set(G[i].y);
        if(rx!=ry)
        {
            sol.push_back({G[i].x, G[i].y});
            cmin+=G[i].c;
            tata[ry]=rx;
        }
    }

    fo<<cmin<<"\n"<<n-1<<"\n";
    for(auto e:sol)
        fo<<e.first<<" "<<e.second<<"\n";

    fi.close();
    fo.close();
    return 0;
}