#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
/*
ifstream in("apm.in");
ofstream out("apm.out");

struct Muchie{
    int s, f, c;
};

vector<Muchie> l;
vector<int> sol;
int n, m, R[1000000], costMin;

bool ordC(Muchie a, Muchie b)
{
    return a.c < b.c;
}

int reprez(int x)
{
    if(R[x] == x)
        return x;
    R[x] = reprez(R[x]);
    return R[x];
}

void reuniune(int x, int y)
{
    R[reprez(x)] = reprez(y);
}

int main()
{
    int a, b, c;
    in>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        in>>a>>b>>c;
        l.push_back({a, b, c});
    }
    sort(l.begin(), l.end(), ordC);
    for(int i = 1; i <= n; i++)
        R[i] = i;
    for(int i = 0; i < l.size(); i++)
        if(reprez(l[i].s) != reprez(l[i].f))
        {
            reuniune(l[i].s, l[i].f);
            costMin += l[i].c;
            sol.push_back(i);
        }
    out<<costMin<<"\n"<<sol.size()<<"\n";
    for(auto it: sol)
        out<<l[it].s<<" "<<l[it].f<<"\n";
    return 0;
}
*/
/*
ifstream in("apm.in");
ofstream out("apm.out");

struct Muchie{
    int s, f, c;
};

vector<Muchie> l;
vector<int> sol;
int n, m, R[1000000], costMin, e1, e2, ok = 1;

bool ordC(Muchie a, Muchie b)
{
    return a.c < b.c;
}

int reprez(int x)
{
    if(R[x] == x)
        return x;
    R[x] = reprez(R[x]);
    return R[x];
}

void reuniune(int x, int y)
{
    R[reprez(x)] = reprez(y);
}

int main()
{
    int a, b, c;
    in>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        in>>a>>b>>c;
        l.push_back({a, b, c});
    }
    sort(l.begin(), l.end(), ordC);
    for(int i = 1; i <= n; i++)
        R[i] = i;
    for(int i = 1; i <= 3; i++)
    {
        cin>>e1>>e2;
        if(reprez(l[i].s) != reprez(l[i].f))
        {
            reuniune(e1, e2);
            l.push_back({e1, e2, 0});
            sol.push_back(l.size() - 1);
        }
        else ok = 0;
    }
    for(int i = 0; i < l.size(); i++)
        if(reprez(l[i].s) != reprez(l[i].f))
        {
            reuniune(l[i].s, l[i].f);
            costMin += l[i].c;
            sol.push_back(i);
        }
    if(ok == 1)
    {
        out<<costMin<<"\n"<<sol.size()<<"\n";
        for(auto it: sol)
            out<<l[it].s<<" "<<l[it].f<<"\n";
    }
    else out<<"Nu se poate";
    return 0;
}
*/
/*
ifstream in("apm.in");
ofstream out("apm.out");
struct Muchii{
    int s, f, c;
}muchie;
vector<Muchii> l;
vector<int> sol, soli, sm;
int n, m, R[10005], cost = 0, costMin = 0, k;
bool ordCost(Muchii a, Muchii b){return a.c < b.c;}
int reprez(int x){
    if(R[x] == x)	return x;
    R[x] = reprez(R[x]);
    return R[x];}
void reuniune(int x, int y){
    R[reprez(x)] = reprez(y);}
int main(){
    int x, y;
    in>>n>>m;
    for(int i = 1; i <= n; i++)
    	R[i] = i;
    for(int i = 1; i <= m; i++)
    {
    	in>>muchie.s>>muchie.f>>muchie.c;
		costMin += muchie.c;
		l.push_back({muchie.s, muchie.f, muchie.c});
    }
    sort(l.begin(), l.end(), ordCost);
    for(int i = 0; i < m; i++){
            if(reprez(l[i].s) != reprez(l[i].f))
            {
                    reuniune(l[i].s, l[i].f);
                    cost += l[i].c;
                    sol.push_back(i);
            }
    }
    out<<"Primul\n"<<"Costul "<<cost<<"\n";
    for(auto it: sol)
       out<<l[it].s<<" "<<l[it].f<<"\n";
    for(int i = 0; i < sol.size(); i++){
        soli.clear();
        for(int i = 1; i <= n; i++)
                R[i] = i;
        cost = 0; k = 0;
        for(int j = 0; j < m; j++)
            if(j !=sol[i])
                if(reprez(l[j].s) != reprez(l[j].f))
                {
                    reuniune(l[j].s, l[j].f);
                    cost += l[j].c;
                    k++;
                    soli.push_back(j);
                }
        if(k == n - 1 && cost < costMin)
        {
            costMin = cost;
            sm = soli;
        }
    }
    out<<"Al doilea\n"<<"Costul "<<costMin<<"\n";
    for(auto it: sm)
       out<<l[it].s<<" "<<l[it].f<<"\n";
    return 0;
}
*/
ifstream in("apm.in");
ofstream out("apm.out");

priority_queue<pair<int, pair<int, int>>> coada;
vector<pair<int, int>> graf[200001];
int n,m, v[200001], cost;

int main()
{
    in >> n >> m;
    int x, y, c;
    while(m)
    {
        in >> x >> y >> c;
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
        m--;
    }

    vector<pair<int, int>> ans;
    for(auto x: graf[1])
        coada.push({-x.second, {1, x.first}});

    v[1] = 1;

    while(!coada.empty())
    {
        x = coada.top().second.first;
        y = coada.top().second.second;
        c = -coada.top().first;
        coada.pop();
        if(v[y]) continue;
        v[y] = 1;
        ans.push_back({x, y});
        cost += c;

        for(auto next: graf[y])
        {
            if(!v[next.first])
                coada.push({-next.second, {y, next.first}});

        }
    }
    out << cost << '\n' << ans.size() << '\n';

    for(auto p: ans)
        out << p.first << ' ' << p.second << '\n';
}