#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second

using namespace std;

ofstream fout("apm.out");
FILE * file;

int n,m,i,x,y,z,nod,t[200001],c;

typedef pair<int,pair<int,int> > pereche;

vector < pair<int,int> > v[200001];

priority_queue <pereche, vector<pereche>, greater<pereche> >pq;

vector < pair<int,int> > ans;

int main()
{
    file = fopen ("apm.in","r");
    fscanf (file, "%d%d", &n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf (file, "%d%d%d", &x,&y,&z);
        v[x].push_back(mp(z,y));
        v[y].push_back(mp(z,x));
    }
    pq.push(mp(0,mp(1,1)));
    t[1]=0;
    while(!pq.empty())
    {
        nod=pq.top().s.s;
        if(t[nod]==0)
        {
            t[pq.top().s.s]=pq.top().s.f;
            c+=pq.top().f;
            ans.push_back(mp(pq.top().s.f,nod));
            pq.pop();
            for(i=0;i<v[nod].size();i++)
                if(t[v[nod][i].s]==0)
                    {
                        pq.push(mp(v[nod][i].f,mp(nod,v[nod][i].s)));
                    }
        }
        else pq.pop();
    }
    fout<<c<<'\n'<<ans.size()-1<<'\n';
    for(i=1;i<ans.size();i++)
        fout<<ans[i].f<<" "<<ans[i].s<<'\n';
    return 0;
}