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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > >h;
vector<pair<int,int> > v[200001];
vector<pair<int,int> > rez;
int n,m,t[200001],i,x,y,c,nod,ct;
int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        v[x].push_back(mp(c,y));
        v[y].push_back(mp(c,x));
    }
    h.push(mp(0,mp(1,1)));
    t[1]=0;
    while(!h.empty())
    {
        nod=h.top().s.s;
        if(t[nod]==0)
        {
            t[h.top().s.s]=h.top().s.f;
            ct+=h.top().f;
            rez.push_back(mp(h.top().s.f,nod));
            h.pop();
            for(i=0; i<v[nod].size(); i++)
                if(t[v[nod][i].s]==0)
                {
                    h.push(mp(v[nod][i].f,mp(nod,v[nod][i].s)));
                }
        }
        else h.pop();

    }
    g<<ct<<'\n'<<rez.size()-1<<'\n';
    for(i=1;i<rez.size();i++)
    {
        g<<rez[i].f<<" "<<rez[i].s<<'\n';
    }
    return 0;
}