#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;
    vector< arc > apcm;
    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;
        Q.erase( Q.begin() );

        viz[u] = 1;

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

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

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

        }
    }

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

    for(int i=1; i<=n; i++)
        if(i != sursa )
        {
          arc a;
          a.v1 = i;
          a.v2 = tata[i];
          a.cost = d[i];

          apcm.push_back(a);
          total += d[i];
        }

    g << total << endl << apcm.size() << endl;
    for(int i=0; i<apcm.size(); i++)
       g << apcm[i].v1 << " " << apcm[i].v2 << 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;
}