#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int n, m, i, j, t[200010], x, y, c, cost, a, b;

int compr(int v)
{
    if(t[v]==v)
        return v;
    t[v]=compr(t[v]);
    return t[v];
}
struct nod
{
    int nr,val,cost;
};
nod p;
vector <nod> M;
vector <nod> sol;
bool cmp(const nod &a,const nod &b)
{
    return a.cost<b.cost;
}
int main()
{
    f>>n>>m;

    for(i=1; i<=n; i++)
        t[i]=i;
    for(i=1;i<=m;i++)
    {
        f>>p.nr>>p.val>>p.cost;
        M.push_back(p);
    }
    sort(M.begin(),M.end(),cmp);

    for(i=0,j=n-1; j; i++)
    {
        a=M[i].nr;
        b=M[i].val;
        x=compr(a);
        y=compr(b);
        if(x!=y)
        {
            t[x]=y;
            cost+=M[i].cost;
            p.nr=a;
            p.val=b;
            sol.push_back(p);
            j--;
        }
    }
     g<<cost<<endl<<n-1<<endl;
    for(i=0;i<sol.size();i++)
        g<<sol[i].val<<" "<<sol[i].nr<<endl;
    return 0;
}