#include <fstream>
#include <vector>
#include <queue>
#include <cstdio>
#define nmax 200010
#define mmax 400010

using namespace std;

short int n,m,i,j;
vector <short int> v[nmax],cost[nmax];
short int nr,costcurent;
struct arbore
{
    short int a,b;
} arbp[mmax];
struct muchie
{
    short int nod1,nod2,cost;
};
bool use[nmax];

class cmp
{
public:
    bool operator()(muchie &a, muchie &b)
    {
        if (a.cost<b.cost)
            return 0;
        return 1;
    }
};
priority_queue <muchie, vector<muchie>, cmp> arb;

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%hd%hd",&n,&m);
    for (i=1; i<=m; i++)
    {
        short int a,b,c;
        scanf("%hd%hd%hd",&a,&b,&c);
        v[a].push_back(b);
        cost[a].push_back(c);
        v[b].push_back(a);
        cost[b].push_back(c);
    }
    short int nrm=0;
    nr++;
    use[1]=1;
    for (i=0; i<v[1].size(); i++)
    {
        muchie x;
        x.nod1=1;
        x.nod2=v[1][i];
        x.cost=cost[1][i];
        arb.push(x);
    }
    while (nr<n)
    {
        while (use[arb.top().nod1]&&use[arb.top().nod2])
            arb.pop();
        muchie x;
        x=arb.top();
        arb.pop();
        nrm++;
        arbp[nrm].a=x.nod1;
        arbp[nrm].b=x.nod2;
        short int nod=x.nod1;
        if (use[x.nod1])
            nod=x.nod2;
        use[nod]=1;
        for (i=0; i<v[nod].size(); i++)
        {
            muchie y;
            y.nod1=nod;
            y.nod2=v[nod][i];
            y.cost=cost[nod][i];
            if (!use[y.nod2])
                arb.push(y);
        }
        nr++;
        costcurent+=x.cost;
    }
    printf("%hd\n%hd\n",costcurent,nrm);
    for (i=1; i<=nrm; i++)
        printf("%hd %hd\n",arbp[i].a,arbp[i].b);
}

/// Foloseste set pentru o solutie mai rapida