#include <fstream>
#include <vector>
#define dmax 2000000000
#include <set>
#include <utility>

using namespace std;

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

vector < pair<int, int> > L[50100];
set < pair<int, int> > ::iterator it;
vector < pair<int, int> > ::iterator itt;
int n,m,i,j,d[200100],v[200100],l[400100],C[400100],t[400100],sum,nr,a,b,c,ok,vmin,poz,S;
pair <int , int > p;
set< pair <int, int> > s;

int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; i ++){
        fin >> a >> b >> c;
        L[a].push_back(make_pair(b,c));
        L[b].push_back(make_pair(a,c));
    }
    for(i=1;i<=n;i++){
        d[i]=dmax;
        s.insert(make_pair(dmax,i));
    }
    d[1]=0;
    s.insert(make_pair(0, 1));
    while(!s.empty()){
        it = s.begin();
        poz = it -> second;
        vmin = it -> first;
        if(vmin == dmax)
            break;
        S += vmin;
        l[++nr] = t[poz];
        C[nr] = poz;
        v[poz] = 1;
        s.erase(it);
         for(itt=L[poz].begin();itt!=L[poz].end();itt++){
            if(d[itt->first]>itt->second&&v[itt->first]==0){
                s.erase(s.find(make_pair(d[itt->first],itt->first)));
                d[itt->first]=itt->second;
                s.insert(make_pair(d[itt->first],itt->first));
                t[itt->first]=poz;
                }

            }
    }
        fout << S << '\n' << nr - 1 << '\n';
        for(i = 2; i <= nr; i ++)
            fout << C[i] << " " << l[i] << '\n';

    return 0;
}