#include <bits/stdc++.h>

using namespace std;

vector <pair <int ,int > > g[200005];
int n,m,viz[200005],s;
priority_queue<pair <int , pair <int ,int > > > q;
vector <pair <int ,int > > sol;
void citire()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
        g[y].push_back(make_pair(x,c));
    }
}
void alg()
{
    viz[1]=1;
    for (vector <pair <int ,int > >:: iterator it=g[1].begin();it!=g[1].end();++it)
        q.push(make_pair(-it->second,make_pair(1,it->first)));
    while (!q.empty())
    {
        int c=-q.top().first;
        int nod1=q.top().second.first;
        int nod2=q.top().second.second;
        q.pop();
        if (viz[nod2])
            continue;
        s+=c;
        viz[nod2]=1;
        sol.push_back(make_pair(nod1,nod2));
        for (vector <pair <int ,int > >:: iterator it=g[nod2].begin();it!=g[nod2].end();++it)
            if (!viz[it->first])
                q.push(make_pair(-it->second,make_pair(nod2,it->first)));
    }
    printf("%d\n%d\n",s,sol.size());
    for(vector <pair <int ,int > > :: iterator it=sol.begin();it!=sol.end();++it)
        printf("%d %d\n",it->first,it->second);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    alg();
    return 0;
}