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

struct multime
{
    int parinte;
    int rank;
}*set;


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

list <cost> citire(int &n, int &m)
{
    int a,b,costul;
    in>>n>>m;
    list <cost> Lc;
    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);
    }
    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(multime *set,int val)
{
    if(set[val].parinte==val) return val;
    return find(set,set[val].parinte);
}

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

int Kruskal(list <cost>Lc, int n)
{
    list <int> *final;
    int s=0;
    set = new multime [n+1];
    final = new list <int> [n+1];
    for(int i=1; i<=n; i++)
    {
        set[i].parinte=i;
        set[i].rank=0;
    }
    auto it=Lc.begin();
    int nr=0;
    int k=0;
    while(k<n-1)
    {
        int a=find(set,(*it).x);
        int b=find(set,(*it).y);
        if(a!=b)
        {
            final[(*it).x].push_back((*it).y);
            s+=((*it).val);
            nr++;
            //final[b].push_back(a);
            reuniune(set,a,b);
            k++;
        }
        it++;
    }
    out<<s<<endl;
    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;
    Lc=citire(n,m);
    Kruskal(Lc,n);
    return 0;
}