#include <bits/stdc++.h>

using namespace std;

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

typedef tuple<int,int,int> edge;

bool cmp(edge a,edge b)
{
    return get<2>(a) > get<2>(b);
}

int n,m,costmin;
list<pair<int,int>>nbr[200010];
bool verif[200010];
priority_queue<edge,vector<edge>,function<bool(edge,edge)>>pq(cmp);
stack<pair<int,int>>ans;

int main()
{
    fin >>n >>m;
    while(m--)
    {
        int a,b,cost;
        fin >>a >>b >>cost;
        nbr[a].push_back({b,cost});
        nbr[b].push_back({a,cost});
    }
    verif[1] = 1;
    for(auto s:nbr[1])
    {
        pq.push({1,s.first,s.second});
    }
    while(!pq.empty())
    {
        int a,b,cost;
        tie(a,b,cost) = pq.top();
        pq.pop();
        if(verif[b])
        {
            continue;
        }
        else
        {
            costmin+=cost;
            ans.push({a,b});
            verif[b] = 1;
            for(auto s:nbr[b])
            {
                if(!verif[s.first])
                {
                    pq.push({b,s.first,s.second});
                }
            }
        }
    }
    fout <<costmin<<"\n"<<ans.size()<<"\n";
    while(!ans.empty())
    {
        fout <<ans.top().first<<" "<<ans.top().second<<"\n";
        ans.pop();
    }
    return 0;
}