#include <fstream>
#include <iostream>
#include <set>
#include <vector>
#define INF 0x3f3f3f3f
#define ZERO 0

using namespace std;

int n;
 vector< vector < pair<int, int> > > la;

void citire()
{
   ifstream f("apm.in");
   int m;
   f >> n >> m;
   la.resize(n+1);

   for(int i=0; i< m; i++)
   {
       int x, y, c;
       f >> x >> y >> c;
       la[x].push_back({y,c});
       la[y].push_back({x,c});
   }
   f.close();
}


void Prim(int sursa)
{
    int u, v, w;
    set < pair <int, int> > Q;
    vector <int> d(n+1, INF);
    vector <int> viz(n+1, ZERO);
    vector <int> tata(n+1, ZERO);

    d[sursa] = 0;
    Q.insert( {d[sursa], sursa} );

    while( !Q.empty() )
    {
        u = Q.begin()->second;
        viz[u] = 1;

        Q.erase( Q.begin() );

        for(int i=0; i<la[u].size(); i++)
        {
            v = la[u][i].first;
            w = la[u][i].second;

            if( viz[v] == 0 && d[v] > w)
            {
                    Q.erase({d[v],v});

                    tata[v] = u;
                    d[v] = w;
                    Q.insert({d[v],v});
            }

        }
    }

    ofstream g("apm.out");
    int total =0;

    for(int i=1; i<=n; ++i)
           total += d[i];

    g << total << '\n' << n-1 << '\n';

    for(int i=1; i<=n; ++i)
        if(i != sursa )
         g << i<< ' ' << tata[i] << '\n';
    g.close();
}

int main(){

	citire();

//	for(int i=1; i<=n; i++)
//    {
//        cout << i << ": ";
//        for(int j=0; j<la[i].size(); j++ )
//          cout << la[i][j].first << "/" << la[i][j].second << " ";
//        cout << endl;
//    }


    Prim(1);

return 0;
}