#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct nod
{
    int x,y,c;
    bool operator()(nod a, nod b)
    {
        return a.c>b.c;
    }
};
vector <nod> g[200010];
priority_queue <nod,vector<nod>,nod> q;
vector <nod> sol;
int m,n;
void citire()
{
    freopen("apm.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        nod q,p;
        scanf("%d %d %d",&q.x,&q.y,&q.c);
        p.x=q.y;
        p.y=q.x;
        p.c=q.c;
        g[q.x].push_back(q);
        g[q.y].push_back(p);
    }
}

int viz[200010];
int vizcoada[200010];
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)
    {
        nod t=q.top();
        q.pop();
        if(viz[t.y]==0)
        {
            nr++;
            sum+=t.c;
            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]);
            viz[t.y]=1;
        }

    }
    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;
}