#include <fstream>
#include<vector>
#include <algorithm>

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector<int> parinte;

int find(int a)
{
    while(a!=parinte[a])
    {
        parinte[a]=parinte[parinte[a]];
        a=parinte[a];
    }
    return a;
}

int connect(int x,int y)
{
    int d=find(x);
    int f=find(y);
    parinte[d]=parinte[f];
}
vector<pair<int,pair<int,int>>> adiacenta;
vector<pair<int,int>> lista;
int main() {
    int n,m;
    cin>>n>>m;
    parinte.resize(n+1);
    int cost_final=0;
    adiacenta.resize(m+1);
    for(int i=0;i<m;i++)
    {
        int nod1,nod2,cost;
        cin>>nod1>>nod2>>cost;
        adiacenta.push_back({cost,{nod1,nod2}});
    }
    sort(adiacenta.begin(),adiacenta.end());
    for(int i=1;i<=n;i++)
        parinte[i]=i;

    for(auto pereche:adiacenta)
    {
        int cost=pereche.first;
        int nod1=pereche.second.first;
        int nod2=pereche.second.second;
        if(find(nod1)!=find(nod2))
        {
            connect(nod1,nod2);
            lista.push_back({nod1,nod2});
            cost_final+=cost;

        }
    }
    cout<<cost_final<<"\n";
    cout<<lista.size()<<"\n";
    for(auto element:lista)
        cout<<element.first<<" "<<element.second<<"\n";

}