#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int fathers[200002];
int sola[400005],solb[400005];

int findd(int x)
{
    if(fathers[x]==x)return x;
    return findd(fathers[x]);
}
void unite(int x,int y)
{
    int fx=findd(x);
    int fy=findd(y);
    fathers[fx]=fy;
}
int main()
{
    int n,m;
    int a,b,w;

    f>>n>>m;
    for(int i=1;i<=n;i++)
        fathers[i]=i;
        vector <  pair  < int  , pair < int, int > > > edges ;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>w;
        edges.push_back(make_pair(w,make_pair(a,b)));

    }
    int mst_weight=0,mst_edges=0;
    int mst_ni=0;

    sort(edges.begin(),edges.end());

    while(mst_edges <  n-1  && mst_ni < n)
    {
        a=edges[mst_ni].second.first;
        b=edges[mst_ni].second.second;
        w=edges[mst_ni].first;

        if(findd(a)!=findd(b))
        {
            unite(a,b);
            mst_weight+=w;
            mst_edges++;
            sola[mst_edges]=a;
            solb[mst_edges]=b;

        }
        mst_ni++;
    }

    g<<mst_weight<<'\n';
    g<<mst_edges<<'\n';
    for(int i=1;i<=mst_edges;i++)
        g<<sola[i]<<' '<<solb[i]<<'\n';

    f.close();g.close();return 0;
    return 0;
}