#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>

#define nmax 200005
using namespace std;
vector< pair < pair <int,int>, int > > v[nmax];
bitset<1> viz[nmax];
vector< pair <int,int> > sol;
struct cmp
{
    bool operator()(pair<pair<int,int>,int> A, pair<pair<int,int>,int> B)
    {
        return A.second>B.second;
    }
};
priority_queue< pair< pair <int,int>,int> , vector <pair <pair <int,int>,int> >, cmp> q;
int n,m;
void read()
{
    scanf("%d %d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
        {scanf("%d %d %d",&x,&y,&z);
         v[x].push_back(make_pair(make_pair(x,y),z));
         v[y].push_back(make_pair(make_pair(y,x),z));
        }
}

void prim()
{
    for(int i=0;i<v[1].size();i++)
        q.push(v[1][i]);
    int tcost=0;
    viz[1]=1;
    while(!q.empty())
    {
        pair < pair<int,int>,int> aux=q.top();
        q.pop();
        if(viz[aux.first.second]==0)
        {
            sol.push_back(aux.first);
            tcost+=aux.second;
            viz[aux.first.second]=1;
            for(int i=0;i<v[aux.first.second].size();i++)
                if(viz[v[aux.first.second][i].first.second]==0)
                    q.push(v[aux.first.second][i]);
        }
    }
    printf("%d\n",tcost);
    printf("%d\n",n-1);
    for(int i=0;i<n-1;i++)
        printf("%d %d\n",sol[i].first,sol[i].second);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    prim();
    return 0;
}