#include <bits/stdc++.h>

using namespace std;

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

const int dim = 2e5 + 7;

bool viz[dim];

vector < pair <int,int> > sol;
vector < pair <int, int> > v[dim];

int n, m, sum;

priority_queue < pair <int, pair <int, int> > > q;

int main()
{
    fin >> n >> m;

    while(m--)
    {
        int x, y, c;
        fin >> x >> y >> c;

        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    viz[1] = 1;
    for(int i = 0; i < v[1].size(); i++)
        q.push({-v[1][i].second,{1,v[1][i].first}});
    while(!q.empty())
    {
       int cost = q.top().first;
       int ant = q.top().second.first;
       int vecin = q.top().second.second;
       q.pop();
       if(viz[vecin] == 1)
            continue;

       viz[vecin] = 1;
       sol.push_back({ant, vecin});
       sum = sum + cost;
       for(int i = 0; i < v[vecin].size(); i++)
       {
           if(viz[v[vecin][i].first] == 0)
           q.push({-v[vecin][i].second, {vecin, v[vecin][i].first}});
       }
    }
    fout << -sum << '\n'<< n-1 << '\n';
    for(int i = 0; i < sol.size(); i++)
        fout << sol[i].first << " " << sol[i].second << '\n';
}