#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 fin("apm.in");
ofstream fout("apm.out");

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

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

int D[nmax];

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()
{
    fin>>N>>M;
    while(M--)
    {

        fin>>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 ;
        abi +=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));
            }


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