#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int nmax=2e5+5;
int n,m,t[nmax],niv[nmax], cost;
vector <pair <int, pair <int,int> > > gr, sol;

struct DSU
{
    void init(int n)
    {
        for (int i=1; i<=n; i++ )
        {
            t[i]=i;
            niv[i]=1;
        }
    }

    int getroot(int x)
    {
        if ( t[x]!=x )
            t[x]=getroot(t[x]);
        return t[x];
    }

    void unite(int x,int y)
    {
        x=getroot(x);
        y=getroot(y);

        if ( x==y ) return;

        if ( niv[x]<niv[y] )
            t[x]=t[y];
        else
        {
            t[y]=t[x];
            if ( niv[x]==niv[y] )
                niv[x]++;
        }
    }

}dsu;

void krusky()
{
    dsu.init(n);
    sort(gr.begin(), gr.end());

    for (auto i:gr )
    {
        int x=dsu.getroot(i.second.first);
        int y=dsu.getroot(i.second.second);

        if ( x!=y )
        {
            dsu.unite(x,y);
            cost+=i.first;
            sol.push_back(i);
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++ )
    {
        int x,y,c; f >> x >> y >> c;
        gr.push_back({c,{x,y}});
        gr.push_back({c,{y,x}});
    }

    krusky();

    g << cost << '\n' << sol.size() << '\n';
    for (auto i:sol )
        g << i.second.first << " " << i.second.second << '\n';
    return 0;
}