#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

priority_queue<pair <int ,pair < int,int >  > > q;
vector < pair  < int ,int > > g[200005],sol;
int viz[200005];

void citire()
{
    int n,m,n1,n2,c;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&n1,&n2,&c);
        g[n1].push_back(make_pair(n2,c));
        g[n2].push_back(make_pair(n1,c));
    }
}
int cost_total;
void solve()
{
    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)));
    viz[1]=1;
    while (!q.empty())
    {
        int nod1=q.top().second.first;
        int nod2=q.top().second.second;
        int cost=-q.top().first;
        q.pop();
        if (!viz[nod2])
        {
            viz[nod2]=1;
            sol.push_back(make_pair(nod1,nod2));
            cost_total+=cost;
            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",cost_total,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();
    solve();
    return 0;
}