#include <fstream>
#include <vector>
#include <queue>

using namespace std;
#define MAXN 200005
#define INF 0x3f3f3f3f

ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m;
int d[MAXN], tata[MAXN];
bool fol[MAXN];
vector< pair<int, int> > graf[MAXN];
priority_queue< pair<int, int> > coada;

void prim(int st)
{
    int i, crt_nod, crt_cost, urm_nod, urm_cost;
    
    for(i=1; i<=n; i++)
        d[i] = INF;
    
    d[st] = 0;
    coada.push( make_pair(0, st) );
    while(!coada.empty())
    {
        crt_nod = coada.top().second; fol[crt_nod] = true;
        crt_cost = -coada.top().first;
        
        coada.pop();
        
        if( crt_cost > d[crt_nod])
            continue;
        
        for(i=0; i<graf[crt_nod].size(); i++)
        {
            urm_nod = graf[crt_nod][i].second;
            urm_cost = graf[crt_nod][i].first;
            if(!fol[ urm_nod ] && d[ urm_nod ] > urm_cost)
            {
                d[ urm_nod ] = urm_cost;
                tata[ urm_nod ] = crt_nod;
                coada.push( make_pair(-urm_cost, urm_nod));
            }
            
        }
    }
    
    int cost_total = 0;
    for(i=1; i<=n; i++)
        cost_total += d[i];
    
    cout<<cost_total<<"\n"<<n-1<<"\n";
    for(i=2; i<=n; i++)
        cout<<i<<" "<<tata[i]<<"\n";
}

int main()
{
    int i, x ,y, z;
    cin >> n >> m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        graf[x].push_back( make_pair(z, y) );
        graf[y].push_back( make_pair(z, x) );
    }
    
    prim(1);
    
    return 0;
}