#include <bits/stdc++.h>
#define pii pair<int,int>
#define piii pair<int,pii >
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
int cost;
bool ap[200005];
vector<pii >nod[200005],ans;
priority_queue<piii ,vector<piii>,greater<piii> >pq;
void add_edges_of(int x)
{
    ///Aici se adauga muchiile ce-l contin pe x in priority_queue
    ap[x]=true;
    int y,c;
    for(int i=0;i<nod[x].size();i++)
    {
        y=nod[x][i].first;
        c=nod[x][i].second;
        if(ap[y])///Daca y apare deja in arborele creat (stiind ca acum l-am adaugat si pe x), nu vom lua muchia (x,y)
            continue;
        pq.push({c,{y,x}});
    }
}
void compute_answer()
{
    add_edges_of(1);///Adaugam primul element al arborelui ca sa avem de unde sa pornim
    int c,x,y;
    while(ans.size()!=n-1)
    {
        c=pq.top().first;
        y=pq.top().second.first;
        x=pq.top().second.second;
        pq.pop();
        if (ap[y])
            continue;
        cost+=c;
        ans.push_back({x,y});///Adaugam muchia (x,y) in raspuns
        add_edges_of(y);///Adaugam noile muchii pe care le putem accesa
    }
}
int main()
{
    fin>>n>>m;
    int c,x,y;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        nod[x].push_back({y,c});
        nod[y].push_back({x,c});
    }
    compute_answer();///cream raspunsul
    ///Afisam raspunsul
    fout<<cost<<"\n";
    fout<<n-1<<"\n";
    for(int i=0;i<ans.size();i++)
        fout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}