#include <fstream>
#include <queue>
#include <vector>
#define PII pair<int,int>
#define st first
#define nd second
#define PB push_back
#define MP make_pair

using namespace std;

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

const int INF = int(2e9);
vector<PII> G[101];
vector<PII>::iterator it;
int n , m , x , y , c , D[101] , cost , T[101];
bool Uz[101];

struct cmp{ bool operator() (const int &x,const int &y)  
	{ return D[x] > D[y]; }
};

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

void read_data()
{
	fin>>n>>m;
	for(;m;m--)
	{
		fin>>x>>y>>c;
		G[x].PB(MP(y,c));
		G[y].PB(MP(x,c));
	}
}

void prim()
{
	fill(D+2,D+n+1,INF);
    H.push(1);
	D[1] = 0;
    Uz[0] = 1;
   for(int vn = n;vn;vn--)
    {
        x = 0;
        while(Uz[x])
        {
            x = H.top();
            H.pop();
        }
        Uz[x] = 1 ;
        cost +=D[x];
        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(it->first);
            }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++) fout<<i<<' '<<T[i]<<'\n';
}

int main()
{
	read_data();
	prim();
	return 0;
}