#include <fstream>
#include <iostream>
#include <vector>
#define s first
#define cost second
#include <queue>
#define pii pair<int,int>

using namespace std;

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

vector <pii > v[200010], apm;
priority_queue< pair <int, pii >  , vector< pair < int, pii > >, greater < pair < int, pii > > > cd;
pair < int, pii > cdtop;



int viz[200010], mviz[500010];

int main ()
{
    int x, y, z, n, m, ans = 0;
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        fin >> x >> y >> z;
        v[x].push_back({z, y});
        v[y].push_back({z, x});
        
    }
    cd.push({0, {0, 1}});
    viz[1] = 0;
    while (!cd.empty())
    {
        if (viz[cd.top().second.second ] == 1)
        {
            cd.pop();
            continue;
        }
        apm.push_back(cd.top().second);
        ans+=cd.top().first;
        cdtop = cd.top();
        viz[cd.top().second.second] = 1;
        cd.pop();
        for (auto it : v[cdtop.second.second])
        {
            if (viz[it.second] == 0)
            {
                cd.push({it.first, {cdtop.second.second, it.second}});
            }
            
        }
        
    }
    fout << ans << '\n' << n-1 << '\n';
    for (int i=1; i<apm.size(); i++)
        fout << apm[i].first << ' ' << apm[i].second << '\n';
    
}