#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <utility>
#include <list>

using namespace std;

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

int inf = 100000;
int q[200001];
int n,m;
int key[200001],tata[200001];
list <pair<int,int>> ad[200001];
int main()
{
    fin >> n >> m;
    for( int i = 1; i <= m ; i++)
    {
        int a,b,c;
        fin >> a >> b >> c;
        ad[a].push_back(make_pair(b,c));
        ad[b].push_back(make_pair(a,c));
    }
    ///initializam nodul de start si costul arborelui
    int s = 1, cost = 0, length = n;
    for(int i = 1; i <= n; i ++)
       {
           key[i] = inf;
           tata[i] = 0;
       }
    key[s] = 0;
    for(int i = 1; i <= n; i++)
        q[i] = 1;
    while(length)
    {
        int mi = inf, node;
        ///gasim nodul cu key minim
        for(int i = 1; i <= n ;i ++)
            if(q[i] == 1 && key[i] < mi)
        {
            mi = key[i];
            node = i;
        }
        ///"stergem" nodul
        q[node] = 0;
        length -- ;
        cost += key[node];
        /// actualizam vectorul key si tata pentru vecinii lui node
        for(auto &edge: ad[node])
        {
           if(q[edge.first] && edge.second < key[edge.first])
           {
               key[edge.first] = edge.second;
               tata[edge.first] = node;
           }
        }
    }
    fout<<cost<<"\n"<< (n - 1) << "\n";
    for(int i = 1; i <= n; i ++)
        if( i != s)
        fout << i << " " << tata[i] << "\n";
    return 0;
}