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

using namespace std;

struct arc{
   int v1, v2;
   double cost;
};

void citire(int& n, vector< vector < pair<int, double> > >& la )
{
   ifstream f("apm.in");
   int m;
   f >> n >> m;
   la.resize(n+1);

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


void Prim(int sursa, const int& n, const vector < vector < pair<int, double> > >& la )
{
    int u, v, w;
    set < pair <double, int> > Q;
    vector <double> 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");
    double total =0;

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


    g << total << endl << n-1 << endl;

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

int main(){

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

	citire(n, la);

//	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,n,la);

return 0;
}