#include <iostream>
#include <bits/stdc++.h>
#define inf 100000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<list<pair<int,int> > >L; //x:(y,c)
vector<int>d, tata, viz;
int n,m;
struct triplet {int x, y, c;};
vector<triplet>APCM;
void Alocari()
{
    L.resize(n+1);
    d.resize(n+1, inf);
    tata.resize(n+1);
    viz.resize(n+1);
}
void Citire()
{
    fin>>n>>m;
    Alocari();
    int x,y,c;
    for(int i=0; i<m; i++)
    {
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
        L[y].push_back(make_pair(x,c));
    }
}

void AfisareArbore()
{
    for(int i=0; i<n-1; i++)
        fout<<APCM[i].x<<" "<<APCM[i].y<<"\n";
}


int main()
{
    Citire();
    set<pair <int,int> >Q;
    d[1]=0;tata[1]=0;
    Q.insert(make_pair(0,1));
    while(!Q.empty())
    {
        pair<int, int> p=*Q.begin();
        Q.erase(Q.begin());
        int nod=p.second;
        int cost=p.first;
        if(!viz[nod])
        {
            viz[nod]=1;
            if(tata[nod]!=0) //pt fiecare nod in afara de primul
            {
                triplet k;
                k.x=nod;
                k.y=tata[nod];
                k.c=cost;
                APCM.push_back(k);
            }
        }
        for(list <pair <int, int> >::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
        {
            int v=(*it).first;
            int w=(*it).second;
            if(viz[v]==0)
            {
                if(w<d[v])
                {
                    tata[v]=nod;
                    Q.erase(make_pair(d[v],v));
                    d[v]=w;
                    Q.insert(make_pair(d[v],v));
                }
            }
        }
    }
    int suma=0;
    for(int i=1; i<=n; i++)
        suma+=d[i];
    fout<<suma<<"\n";
    fout<<n-1<<"\n";
    AfisareArbore();
    return 0;
}