#include <bits/stdc++.h>
#define inf INT_MAX
#define nmax 200001
using namespace std;
vector <pair <int, int> > v[2*nmax];
vector <int > cost(nmax,inf);
set <pair <int, int> > q;
struct muchie {int x, y, pr;};
pair <int, int> p[nmax];
int z[nmax];
int main()
{
    int n, m, i, j, x, y, c;
   ifstream f("apm.in");
   ofstream g("apm.out");
   f >> n >> m;
   for (i=1;i<=m;++i)
   {
       f >> x >> y >> c;
       v[x].push_back(make_pair(y,c));
       v[y].push_back(make_pair(x,c));
   }
   q.insert(make_pair(0,1));
   int vf, gr;
   z[1]=1;
while (!q.empty())
{
    i=(*q.begin()).second;
    q.erase(q.begin());
    vector <pair <int, int> >:: iterator it;
    for (it=v[i].begin();it!=v[i].end();++it)
    {
        vf=(*it).first;
        gr=(*it).second;
        if (cost[vf]>gr&&  vf!=p[i].first)
        {
        if (cost[vf]!=inf)
            q.erase(q.find(make_pair(cost[vf],vf)));


        p[vf].first=i;
        p[vf].second=gr;
        cost[vf]=gr;
        q.insert(make_pair(gr,vf));
        z[vf]=1;

        }

    }
}
int sum=0;
for (i=2;i<=n;++i)
{
    sum+=p[i].second;
}
g << sum << "\n" << n-1 << "\n";
for (i=2;i<=n; ++i)
g << i << " " << p[i].first << "\n";
    return 0;
}