#include<bits/stdc++.h>

using namespace std;

#define muchie pair<int,int>

class graf
{
    int n,m,x,y,c,px,py,costtotal=0;
    vector <pair <int,muchie> > G,MST;
    vector <int> parinti;
    int gasit(int x);
public:
    graf(char* infile);
    void mst(char *outfile);
};

graf::graf(char *infile)
{
    int i;
    ifstream f(infile);
    f>>n>>m;
    for(i=0;i<=n;i++)
        parinti.push_back(i);
    for(i=0;i<=m;i++)
    {
        f>>x>>y>>c;
        G.push_back(pair<int,muchie>(c,make_pair(x,y)));
    }

}

int graf::gasit(int x)
{
    if(x!=parinti[x])
        parinti[x]=gasit(parinti[x]);
    return parinti[x];
}

void graf::mst(char *outfile)
{
    ofstream g(outfile);
    sort(G.begin(),G.end());
    for(int i=0;i<m;i++)
    {
        px=gasit(G[i].second.first);
        py=gasit(G[i].second.second);
        if((px)!=(py))
        {

            MST.push_back(G[i]);
            costtotal+=G[i].first;
            parinti[px]=parinti[py];
        }
    }
    g<<costtotal<<endl<<MST.size()<<endl;
    for(int i=0;i<MST.size();i++)
        g<<MST[i].second.second<<" "<<MST[i].second.first<<endl;

}



int main()
{
    graf X("apm.in");
    X.mst("apm.out");
    return 0;
}