#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];

struct cmp{

public :
            inline bool operator ()(const pair<int,int> &x,const pair<int,int> &y){return x.second>y.second; }
};

priority_queue<pair<int,int>, vector<pair <int,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(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;
}