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

#define NMAX 200005
#define MMAX 400005

using namespace std;
vector<pair<int,int> > graf[NMAX];
vector<pair<int,int> > rez;
int N,M;
int sum;

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


priority_queue<pair<int, int> > q;
int viz[NMAX];
int t[NMAX];
int d[NMAX];
void prim()
{
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int nod_curent = q.top().second;
        int cost_curent = -q.top().first;
        q.pop();
        if(viz[nod_curent] || cost_curent!=d[nod_curent])
            continue;

        viz[nod_curent]=1;
        sum += d[nod_curent];
        rez.push_back(make_pair(nod_curent,t[nod_curent]));

        for(vector<pair<int,int> >::iterator ii = graf[nod_curent].begin();ii!=graf[nod_curent].end();ii++)
        {
            int nod_nou = ii->first;
            int cost_nou = ii->second;
            if(cost_nou > d[nod_nou] && d[nod_nou]!=0)
                continue;

            d[nod_nou]=cost_nou;
            t[nod_nou]=nod_curent;
            q.push(make_pair(-cost_nou,nod_nou));

        }
    }
}


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

    printf("%d\n%d\n",sum,rez.size()-1);
    for(vector<pair<int,int> >::iterator ii = rez.begin()+1;ii!=rez.end();ii++)
        printf("%d %d\n",ii->first,ii->second);
    return 0;
}