#include <fstream>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
const int nmax=2e5+3;
int n,m,a,b,c,ant,nod,cost;
vector <pair <int,int> > sol;
bool viz[nmax],am[nmax];
vector <pair <int,int> > v[nmax];
priority_queue < pair < pair <int,int>,int> > q;
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>a>>b>>c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    for(int i=0;i<v[1].size();++i) q.push({{-v[1][i].x,v[1][i].y},1});
    viz[1]=1;
    while(!q.empty())
    {
        nod=q.top().x.y;
        c=q.top().x.x;
        ant=q.top().y;
        q.pop();
        if(viz[nod]) continue;
        viz[nod]=1;
        cost-=c;
        sol.push_back({nod,ant});
        for(int i=0;i<v[nod].size();++i)
        {
            if(!am[v[nod][i].y]) q.push({{-v[nod][i].x,v[nod][i].y},nod});
        }
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(int i=0;i<sol.size();++i) g<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}