#include<iostream>
#include<fstream>
#include<vector>
#include<ctime>
#include<cstdlib>
#define numaru 200001
#define INFILE "apm.in"
#define OUTFILE "apm.out"
using namespace std;
typedef struct {int val,i,j;}MUCHIE;
vector < pair<int, int> > Graf[numaru], MST[numaru];
vector < MUCHIE > min_heap;
int n,dim,sum;
bool einMST[numaru];
MUCHIE createMUCHIE(int val,int i,int j)
{
    MUCHIE muchie;
    muchie.val=val;
    muchie.i=i;
    muchie.j=j;
    return muchie;
}

void swapinheap(int i,int j)
{
    MUCHIE auxmuchie;
    auxmuchie=min_heap[i];min_heap[i]=min_heap[j];min_heap[j]=auxmuchie;
}

void min_heapADD(MUCHIE muchie)
{
    if(dim==0)
    {
        min_heap.push_back(muchie);
        dim=1;
    }
    else
    {
        ++dim;
        min_heap.push_back(muchie);
        int i=dim;
        while(i!=1 && min_heap[i].val<min_heap[i/2].val)
        {
            swapinheap(i,i/2);
            i/=2;
        }
    }
}

void min_heapDELETEHEAD()
{
    if(dim==0)return ;
    swapinheap(1,dim);
    min_heap.erase(min_heap.begin()+dim);
    --dim;
    for(int i=1;i*2<=dim;)
    {
        i*=2;
        if(i+1<=dim && min_heap[i+1].val<min_heap[i].val)++i;
        if(min_heap[i].val<min_heap[i/2].val) swapinheap(i,i/2);
        else break;
    }
}
void citire()
{
    ifstream f(INFILE);
    int m,i,j,c;
    f>>n>>m;
    for(;m;--m)
    {
        f>>i>>j>>c;
        Graf[i].push_back(make_pair(j,c));
        Graf[j].push_back(make_pair(i,c));
    }
    f.close();
}

void scrieGraf(char *s,vector< pair<int, int> > A[numaru])
{
    ofstream g(s);
    g<<sum<<"\n"<<n-2<<"\n";
    for(int i=1;i<=n;++i)
        for(int j=0;j<A[i].size();++j)if(i!=A[i][j].first)g<<i<<","<<A[i][j].first<<"\n",
    g.close();
}

void extractMST()
{
    int x;
    MUCHIE muchia;
    ///aleg random un nod start
    ///x=rand()%n+1;
    x=1;///inca nu
    ///il marchez ca fiind in MST
    einMST[x]=true;
    ///ii adaug muchiile adiacente in min_heap
    for(int i=0;i<Graf[x].size();++i)
        min_heapADD(createMUCHIE(Graf[x][i].second,x,i));
    for(int step=n;step!=1;--step)
    {
        do
        {
            muchia=min_heap[1];
            min_heapDELETEHEAD();
        }
        while(einMST[muchia.i] && einMST[Graf[muchia.i][muchia.j].first]);
        ///acum am scos muchie de la muchia.i la Graf[muchia.i][muchia.j].first de valoare Graf[muchia.i][muchia.j].second
        sum+=muchia.val;
        ///adaug muchia in MST
        MST[muchia.i].push_back(Graf[muchia.i][muchia.j]);
        MST[Graf[muchia.i][muchia.j].first].push_back(make_pair(muchia.i,Graf[muchia.i][muchia.j].second));
        ///il marchez ca fiind in MST
        einMST[x]=true;
        for(int i=0;i<Graf[x].size();++i)
            if(!einMST[Graf[x][i].first])
                min_heapADD(createMUCHIE(Graf[x][i].second,x,i));
    }
}
int main()
{
    min_heap.push_back(createMUCHIE(-1,-1,-1));
    //srand(time(0));

    citire();
    extractMST();
    scrieGraf(OUTFILE,MST);
    return 0;
}