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

#define NMAX 200005
#define MMAX 500005

using namespace std;

int N,M;
vector<pair<int,int> > graf[NMAX];
priority_queue<pair<int,pair<int,int> > > q;
vector<pair<int,int> > rez;
int suma;
int used[NMAX];
void citire()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        graf[x].push_back(make_pair(y,c));
        graf[y].push_back(make_pair(x,c));
    }
}

void prim()
{
    for(vector<pair<int,int> >::iterator ii = graf[1].begin();ii!=graf[1].end();ii++)
        q.push(make_pair(-ii->second,make_pair(1,ii->first)));
    used[1]=1;
    while(!q.empty())
    {
        int nod_curent = q.top().second.second;
        int tata_curent = q.top().second.first;
        int cost_curent = -q.top().first;
        q.pop();

        if(used[nod_curent])
            continue;

        used[nod_curent]=1;
        suma+=cost_curent;
        rez.push_back(make_pair(tata_curent,nod_curent));

        for(vector<pair<int,int> >::iterator ii = graf[nod_curent].begin();ii!=graf[nod_curent].end();ii++)
            if(!used[ii->first])
                q.push(make_pair(-ii->second,make_pair(nod_curent,ii->first)));
    }
}

void afisare()
{
    printf("%d\n%d\n",suma,rez.size());
    for(vector<pair<int,int> >::iterator ii=rez.begin();ii!=rez.end();ii++)
        printf("%d %d\n",ii->first,ii->second);
}


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