#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;


int main()
{
    vector< pair <int, pair<int, int> > > v,t;
    vector < pair <int, int> > graph[100005];
    priority_queue < pair <int, pair<int, int> > >pq;
    int n,m;
    int a,b,c;
    ifstream f("apm.in");
    f>>n>>m;
    for(int i=0; i<m; i++)
    {
        f>>a>>b>>c;
        c=-c;
        v.push_back(make_pair(c, make_pair(a,b)));
        graph[a].push_back(make_pair(b,c));
        graph[b].push_back(make_pair(a,c));
    }
    int sursa =1;
    int viz[100005];
    for(int i=1; i<=n; i++)
        viz[i]=0;
    for(int i=0; i<m; i++)
    {
        int k;
        k=(v[i].second).first;
        int y=(v[i].second).second;
        if (k==1 || y==1)
            pq.push(v[i]);
    }
    viz[1]=1;
    int s=0;
    while(!pq.empty())
    {
        pair <int, pair<int, int> > best;
        best=pq.top();
        pq.pop();
        int nod1,nod2;
        int cost;
        cost=best.first;
        nod1=(best.second).first;
        nod2=(best.second).second;
        if(viz[nod1] && viz[nod2])
            continue;
        else
        {   s++;
            t.push_back(best);
            if(viz[nod1]!=1)
            {
                int lim=graph[nod1].size();
                for(int i=0;i<lim;i++)
                {
                    int vecin=graph[nod1][i].first;
                    int cost=graph[nod1][i].second;
                    pq.push(make_pair(cost,make_pair(nod1,vecin)));
                }

                viz[nod1]=1;
            }
            if(viz[nod2]!=1)
            {
                int lim=graph[nod2].size();
                for(int i=0;i<lim;i++)
                {
                    int vecin=graph[nod2][i].first;
                    int cost=graph[nod2][i].second;
                    pq.push(make_pair(cost,make_pair(nod2,vecin)));
                }
                viz[nod2]=1;
            }
        }
    }
    ofstream g("apm.out");
    int w=0;
        for(int i=0;i<s;i++)
    {
        w=t[i].first+w;
    }
    g<<-w<<endl<<s<<"\n";
    for(int i=0;i<s;i++)
    {

        g<<(t[i].second).first<<" "<<(t[i].second).second;
        g<<"\n";
    }

}