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


int main()
{
    vector< pair <int, pair<int, int> > > v,t;
    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)));
        // pq.push(make_pair(c, make_pair(a,b)));
    }
    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;
        // pair <int, pair<int, int> > x;
        //x=v[i];
        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)
            {
                for(int i=0; i<m; i++)
                {
                    int k;
                    // pair <int, pair<int, int> > x;
                    //x=v[i];
                    k=(v[i].second).first;
                    int y=(v[i].second).second;
                    if (k==nod1 || y==nod1)
                        pq.push(v[i]);}

                viz[nod1]=1;
            }
            if(viz[nod2]!=1)
            {
                for(int i=0; i<m; i++)
                {
                    int k;
                    // pair <int, pair<int, int> > x;
                    //x=v[i];
                    k=(v[i].second).first;
                    int y=(v[i].second).second;
                    if (k==nod2 || y==nod2)
                        pq.push(v[i]);
                }
                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<<endl;
    for(int i=0;i<s;i++)
    {

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

}