#include <iostream>
#include <list>
#include <fstream>
using namespace std;

ifstream in ("apm.in");
ofstream out ("apm.out");


struct cost
{
    int x;
    int y;
    int val;
};

int *parinte;

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

list <cost> citire(list <int> *&Ladiac,int &n, int &m)
{
    int a,b,costul;
    in>>n>>m;
    list <cost> Lc;
    Ladiac = new list <int> [n+1];
    for(int i=1; i<=m; i++)
    {
        in>>a>>b>>costul;
        cost z;
        z.x=a;
        z.y=b;
        z.val=costul;
        Lc.push_back(z);
        Ladiac[a].push_back(b);
    }
    Lc.sort(compare);
    return Lc;
}


int afisare(list <cost> Lc,int n)
{
    for(auto it=Lc.begin(); it!=Lc.end(); it++)
    {
        out<<"Muchia "<<(*it).x<<" "<<(*it).y<<" are costul "<<(*it).val<<endl;
    }
}

int find(int *parinte,int val)
{
    if(parinte[val]==-1) return val;
    return find(parinte,parinte[val]);
}

int reuniune(int *parinte,int x,int y)
{
    int px=find(parinte,x);
    int py=find(parinte,y);
    parinte[px]=py;
}

int Kruskal(list <cost>Lc, int n)
{
    list <int> *final;
    int s=0;
    parinte = new int[n+1];
    final = new list <int> [n+1];
    for(int i=1; i<=n; i++) parinte[i]=-1;
    auto it=Lc.begin();
    while(it!=Lc.end())
    {
        int a=find(parinte,(*it).x);
        int b=find(parinte,(*it).y);
        if(a!=b)
        {
            final[(*it).x].push_back((*it).y);
            s+=((*it).val);
            //final[b].push_back(a);
            reuniune(parinte,a,b);
            it++;
        }
        else
        {
            it++;
        }
    }
    out<<s<<endl;
    int nr=0;
    for(int i=1; i<=n; i++)
    {
        if(!final[i].empty()){
        {
            for(auto it=final[i].begin(); it!=final[i].end(); it++)
            {
                nr++;
            }
        }
        }
    }
    out<<nr<<endl;
    for(int i=1; i<=n; i++)
    {
        if(!final[i].empty()){
        {
            for(auto it=final[i].begin(); it!=final[i].end(); it++)
            {
                out<<i<<" "<<*it<<" ";
                out<<endl;
            }
        }
        }
    }
    return 1;
}


int main()
{
    int n,m;
    list <cost>Lc;
    list <int>*Ladiac;
    Lc=citire(Ladiac,n,m);
    //afisare(Lc,n);
    Kruskal(Lc,n);
    return 0;
}