#include <fstream>
#include <bits/stdc++.h>

using namespace std;

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

int N, M;
int cost_total;
vector< pair<int, pair<int,int> > > G;
vector<int> tati;
vector<int> rang;
vector<pair<int,int>> afis;

void Citire()
{
    int x,y,c;
    for(int i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        G.push_back({c,{x,y}});
    }
}

int find(int nod) ///returnez tatal nodului nod
{
    if(nod!=tati[nod])
        tati[nod]=find(tati[nod]);
    return tati[nod];
}

void Uniune(int x, int y)
{
    x=find(x);
    y=find(y);
    ///Unesc subarborele cu inaltimea mai mica la cel mai mare

    if(rang[x]>rang[y])
        tati[y]=x;
    else
        tati[x]=y;
    if(rang[x]==rang[y])
        rang[y]++;
}

void Kruskal()
{
    //Sortez in ordine crescatoare dupa cost
    sort(G.begin(),G.end());
    vector< pair< int, pair< int, int> > >::iterator it;
    for(it=G.begin();it!=G.end();it++)
    {
        int u=it->second.first;
        int v=it->second.second;

        int set_u=find(u);
        int set_v=find(v);

        ///Verific daca se creaza cicluri, daca nu intru in if
        if(set_u!=set_v)
        {
            //fout<<u<<" "<<v<<endl;
            afis.push_back({u,v});
            cost_total+=it->first;
            Uniune(set_u,set_v);
        }
    }
}

int main()
{
    fin>>N>>M;
    G.resize(M+1);
    Citire();
    tati.resize(N+1);
    for(int i=1;i<=N;i++)
        tati[i]=i;
    rang.resize(N+1,0);
    //afis.resize(N);
    Kruskal();
    fout<<cost_total<<endl<<N-1<<endl;
    vector<pair<int,int>>::iterator it;
    for(it=afis.begin();it!=afis.end();it++)
        fout<<it->first<<" "<<it->second<<endl;
}