#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;


struct muchie
{
    int x,y,c;
    bool operator()(muchie a, muchie b)
    {
        return a.c>b.c;
    }
};

vector <muchie> g[200020];
priority_queue <muchie,vector<muchie>,muchie> q;
int n,m;


void citire()
{
    freopen("apm.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        muchie b,a;
        scanf("%d %d %d",&b.x,&b.y,&b.c);
        a.x=b.y;
        a.y=b.x;
        a.c=b.c;
        g[b.x].push_back(b);
        g[a.x].push_back(a);

    }

}

int s,nr;
int viz[200020];
vector <muchie> sol;
void apm()
{
    for(int i=0;i<g[1].size();i++)
        q.push(g[1][i]);
    viz[1]=1;
    while(nr<n-1)
    {
        muchie t=q.top();
        q.pop();
        if(!viz[t.y])
        {
            s+=t.c;
            nr++;
            viz[t.y]=1;
            sol.push_back(t);
            for(int i=0;i<g[t.y].size();i++)
                if(!viz[g[t.y][i].y])
                    q.push(g[t.y][i]);

        }

    }

}

void afisare()
{
    printf("%d\n%d\n",s,nr);
    for(int i=0;i<sol.size();i++)
        printf("%d %d\n",sol[i].x,sol[i].y);

}

int main()
{
    freopen("apm.out","w",stdout);
    citire();
    apm();
    afisare();
    return 0;
}