#include <fstream>
#include <vector>
#include <queue>
#define nmax 200002
#define oo 9999

using namespace std;

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

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

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

struct cmp{

public :
            inline bool operator ()(const int&x,const int&y){return D[x]>D[y];}
};

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

bool Uz[nmax];

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(1);
    Uz[0] = 1;
    In_Heap[1] = 1;
    while(vn)
    {
        x = 0;
        while(Uz[x])
        {
            x = H.top();
            H.pop();
        }
        Uz[x] = 1 ;
        cost +=D[x];
        vn--;
        In_Heap[x] = 0;
        for(it = G[x].begin();it!=G[x].end();++it)
            if(it->second<D[it->first])
            {
                T[it->first] = x;
                D[it->first] = it->second;
                if(In_Heap[it->first]==0)
                    H.push(it->first),In_Heap[it->first]=1;
            }


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