#include<iostream>
#include<fstream>
#include<queue>
#include<algorithm>
struct muchie { int e1, e2; short c;};

bool comp(muchie a, muchie b) { return(a.c<b.c);}
using namespace std;

int main() {
ifstream f("apm.in"); ofstream h("apm.out");
int n,m;
f >> n >> m; muchie g[m+1]; int v[n+1];
for (int i=1; i<=m; i++) { f >>g[i].e1>>g[i].e2>>g[i].c;} f.close();
sort(g+1, g+m+1, comp);
for (int i=1; i<=n; i++) { v[i]=i;}
int k=0, j=1, cost=0, v1,v2;  int nr=0;
queue<int> b,d; 
int x; for (int i=1; i<=m; i++) { cout << g[i].c <<"  ";}
while (k<n-1) 
{
   if (v[g[j].e1]!=v[g[j].e2]) 
   { k+=1; cost+=g[j].c;
     x=g[j].e1;  b.push(x); 
     x=g[j].e2; d.push(x); nr+=1;
     v1=v[g[j].e1]; v2=v[g[j].e2];
     for (int p=1; p<=n; p++) { if (v[p]==v1) v[p]=2;}
     }
  j+=1;  
}
h << cost <<"\n"; h << nr << "\n";
while (!b.empty()) { h << b.front() <<" "<< d.front()<<"\n"; 
b.pop(); d.pop();}
h.close(); 
cin.ignore(2);
return(0);
}