#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g ("apm.out");
vector<pair<int,int>>adiacenta[100001];
int n,m,cost_total;
bool viz[100001];
vector<pair<int,int>>rasp;
priority_queue<pair<int,pair<int,int>>, vector< pair<int,pair<int,int>> >, greater< pair<int,pair<int,int>>>>q;
void citire()
{
    f >> n >> m;
    for(int i = 1; i<=m; i++)
    {
        int x,y,c;
        f >> x>> y>>c;
        adiacenta[x].push_back({y,c});
        adiacenta[y].push_back({x,c});
    }
}
int main()
{
    citire();
    q.push({0,{0,1}});
    while(!q.empty())
    {
        int cost = q.top().first;
        int nod1 = q.top().second.first;
        int nod2 = q.top().second.second;
        q.pop();
        if(viz[nod2]==1)
            continue;
        viz[nod2] = 1;
        cost_total+=cost;
        rasp.push_back({nod1,nod2});
        for(auto x:adiacenta[nod2])
        {
            int nod = x.first;
            int cost1 = x.second;
            if(!viz[nod])
            q.push({cost1,{nod2,nod}});

        }
    }
    g<< cost_total<<'\n'<<rasp.size()-1<<'\n';
    vector<pair<int,int>>::iterator it;
    for(it = rasp.begin()+1;it!=rasp.end();it++)
        g << it->first<< " "<< it->second<<'\n';

}