#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#define INF 200002

using namespace std;

struct edge
{
    int x,y,c;
};

class cmp
{
    public: bool operator()(const edge &e1,const edge &e2)
    {
        return e1.c>e2.c;
    }
};

vector< pair<int,int> > graph[INF];
vector<edge> ras;
priority_queue<edge, vector<edge>, cmp> Q;
int n,m,nr=0,cost=0;
bool check[INF];

void expand()
{
    while(Q.size()>0)
    {
        int nod=Q.top().y;
        if(check[nod]){Q.pop();continue;}
        check[nod]=1;
        ++nr;
        ras.push_back(Q.top());
        cost+=Q.top().c;

        for(int i=0;i<graph[nod].size();++i)
        {
            int nod2=graph[nod][i].first;
            int c=graph[nod][i].second;
            edge e;e.x=nod;e.y=nod2;e.c=c;
            Q.push(e);
        }
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);

    for(int i=0;i<m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        graph[x].push_back(make_pair(y,c));
        graph[y].push_back(make_pair(x,c));
    }

    check[1]=1;
    nr=1;
    for(int i=0;i<graph[1].size();++i)
    {
        int nod=graph[1][i].first;
        edge e;e.x=1;e.y=nod;e.c=graph[1][i].second;
        Q.push(e);
    }
    while(ras.size()<n-1)expand();
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(int i=0;i<n-1;++i)printf("%d %d\n",ras[i].x,ras[i].y);
    return 0;
}