#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define NMax 1000005
#define mp make_pair
#define piii pair<int,pair<int,int>>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int t[NMax];
int h[NMax];
int n,m,sum=0,cnt=0;

vector <pair<int,int>> rez;
priority_queue <piii, vector<piii>, greater<piii>> pq;

int rad(int nod)
{
    int cnod=nod;
    while(t[nod]!=0)
        nod=t[nod];
    while(t[cnod]!=0)
        {
            int aux=t[cnod];
            t[cnod]=nod;
            cnod=aux;
        }
    return nod;
}

void reuniune (int x, int y)
{
    if(h[x]>h[y])
        t[y]=x;
    else
        t[x]=y;
    if(h[x]==h[y])
        h[y]++;
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
       int x,y,c;
       fin>>x>>y>>c;
       pq.push({c,{x,y}});
    }
    while(!pq.empty())
    {
        int c=pq.top().first;
        int x=pq.top().second.first;
        int y=pq.top().second.second;
        pq.pop();
        int rx=rad(x);
        int ry=rad(y);
        if(rx!=ry)
        {
            sum+=c;
            cnt++;
            rez.push_back({x,y});
            reuniune(rx,ry);
        }
    }
    fout<<sum<<"\n"<<cnt<<"\n";
    for(auto i: rez)
    {
        fout<<i.first<<" "<<i.second<<"\n";
    }
    return 0;
}