#include <bits/stdc++.h>


using namespace std;

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

priority_queue <pair <int,int>> pq;
vector <pair<int,int>> graf[50001];
pair<int,int> sol[50001];

int n,m, viz[50001],s,k=1;

void citire() {
    int x,y,c;
    fin >> n >> m;
    for (int i=1;i<=m;i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y,c});
        graf[y].push_back({x,c});
    }
}

void apm(){
    int nod;
    pq.push({0,1});
    nod=1;
    while (!pq.empty())
    {
        pq.pop();
        viz[nod]=1;
        for (pair <int,int> el: graf[nod])
        {
            if(viz[el.first]==0)
            {
                pq.push({-el.second,el.first});
            }
        }
        if(!viz[pq.top().second]) {
            sol[k]={nod,pq.top().second};
            k++;
            nod=pq.top().second;
            s=s-pq.top().first;
            }
        }
}

int main()
{
    citire();
    apm();
    fout << s << "\n" << n-1 << "\n";
    for (int i=1;i<k;i++) {
        fout << sol[i].first << " " << sol[i].second <<"\n";
    }
}