#include <fstream>
#include <queue>
#include <utility>
using namespace std;
vector<pair<short,int> > tb[200002];
int x,y,c,i,n,m,viz[200002],apm[200002],cost,j;
priority_queue<pair<short,pair<int,int> >,vector<pair<short,pair<int,int> > >,greater<pair<short,pair<int,int> > > > p;
int main ()
{int i;
ifstream f("apm.in");
f>>n>>m;
for(i=1;i<=n;i++)
tb[i].push_back(make_pair(0,0));
for(i=1;i<=m;i++)
{f>>x>>y>>c;
tb[x][0].second++;
tb[x].push_back(make_pair(c,y));
tb[y][0].second++;
tb[y].push_back(make_pair(c,x));
}
f.close();
for(i=1;i<=tb[1][0].second;i++)
p.push(make_pair(tb[1][i].first,make_pair(1,tb[1][i].second)));
viz[1]=1;
for(i=1;i<n;i++)                 
{y=p.top().second.second;
 if(!viz[y])
 {viz[y]=1;
 apm[y]=p.top().second.first;
 cost+=p.top().first;
 p.pop();}
 else {p.pop(); i--; continue;}

for(j=1;j<=tb[y][0].second;j++)
p.push(make_pair(tb[y][j].first,make_pair(y,tb[y][j].second)));
}

ofstream g("apm.out"); 
g<<cost<<'\n';
g<<n-1<<'\n';
for(i=2;i<=n;i++)
g<<i<<" "<<apm[i]<<'\n';
  g.close();
return 0;
}