#include <iostream>
#include <list>
#include <fstream>
#include <algorithm>
#include<cstdio>
#include <vector>
using namespace std;



struct cost
{
    int x;
    int y;
    int val;
    int ok=0;
};

struct multime
{
    int parinte;
    int rang;
};


bool compare(cost a, cost b)
{
    return a.val < b.val;
}

vector <cost> citire(int &n, int &m)
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int a,b,costul;
    scanf("%d%d",&n,&m);
    //in>>n>>m;
    vector <cost> Lc;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&costul);
        //in>>a>>b>>costul;
        cost z;
        z.x=a;
        z.y=b;
        z.val=costul;
        z.ok=0;
        Lc.push_back(z);
    }
    sort(Lc.begin(),Lc.end(),compare);
    return Lc;
}

int find(multime *set,int val)
{
    while(set[val].parinte!=val)
        val=set[val].parinte;
    return val;
}

int reuniune(multime *set,int a,int b)
{
    if(set[a].rang < set[b].rang)
        set[a].parinte=b;
    else if(set[a].rang > set[b].rang)
        set[b].parinte=a;
    else if(set[a].rang == set[b].rang)
    {
        set[b].parinte=a;
        set[a].rang++;
    }
    return 1;
}

int Kruskal(vector <cost>Lc, int n)
{
    int s=0;
    multime *set = new multime [n+1];
    for(int i=1; i<=n; i++)
    {
        set[i].parinte=i;
        set[i].rang=0;
    }
    auto it=Lc.begin();
    int nr=0;
    int k=0;
    while(k<n-1)
    {
        int x=(*it).x;
        int y=(*it).y;
        int a=find(set,x);
        int b=find(set,y);
        if(a!=b)
        {
            (*it).ok=1;
            s+=((*it).val);
            nr++;
            reuniune(set,a,b);
            k++;
        }
        it++;
    }
    printf("%d\n%d\n",s,nr);
    //out<<s<<endl;
    //out<<nr<<endl;
    for(auto it=Lc.begin();it!=Lc.end();it++)
    {
        if((*it).ok==1)
            printf("%d %d\n",(*it).x,(*it).y);
            //out<<(*it).x<<" "<<(*it).y<<endl;
    }
    return 1;
}

int main()
{
    int n,m;
    vector <cost> Lc;
    Lc=citire(n,m);
    Kruskal(Lc,n);
    return 0;
}