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

using namespace std;

struct muchie
{
    int x,y,c;
};

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

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

void citire()
{

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

void prim()
{
    int sum=0;
    int nr=0;
    viz[1]=1;
    for(int i=0;i<g[1].size();i++)
        q.push(g[1][i]);
    while(nr<n-1)
    {
        muchie t=q.top();
        q.pop();
        if(!viz[t.y]  )
        {
            nr++;
            sum+=t.c;
            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]);
        }
    }

    freopen("apm.out","w",stdout);
    printf("%d\n%d\n",sum,nr);
    for(int i=0;i<sol.size();i++)
        printf("%d %d\n",sol[i].x,sol[i].y);

}

int main()
{
    citire();
    prim();
    return 0;
}