#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#define nmax 200002
#define oo 999999
#define PII pair<int, int>
using namespace std;

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

vector< pair<int,int> > G[nmax];
vector< pair<int,int> > ::iterator it;

int N,M,x,y,c,vn,cost;
int T[nmax];
bool Uz[nmax];

int D[nmax];

/**
struct cmp{

public :
            inline bool operator ()(const int &x,const int &y){
                   if(D[y] != D[x]) {
                        return D[y] < D[x];
                   }
                   else {
                        return D[x] < D[y];
                   }
            }
};
**/

struct cmp{
     bool operator()(const  PII &x, const PII &y) const {
         return x.second > y.second;
     }
};

priority_queue<PII, vector<PII>, cmp> H;

int main()
{
    in>>N>>M;
    while(M--)
    {
        in>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }
    vn = N;
    fill(D+2,D+N+1,oo);
    H.push(make_pair(1, 0));
    Uz[0] = 1;
    while(vn)
    {
        x = 0;
        while(Uz[x])
        {
            x = H.top().first;
            H.pop();
        }
        Uz[x] = 1 ;
        cost +=D[x];
        vn--;
        for(it = G[x].begin();it!=G[x].end();++it)
            if(it->second<D[it->first] && Uz[it->first]==0)
            {
                T[it->first] = x;
                D[it->first] = it->second;
                H.push(make_pair(it->first, it->second));
            }


    }
    out<<cost<<'\n'<<N-1<<'\n';
    for(int i=2;i<=N;i++)out<<i<<' '<<T[i]<<'\n';
    return 0;
}