#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMax 200001
using namespace std;
vector<pair< pair <int,int> ,int> >Graf;
vector<pair<int,int> > cost[NMax],sol;
int N,M,x,y,z,rez;
int mark[NMax];

void Read()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        cost[x].push_back(make_pair(y,z));
        cost[y].push_back(make_pair(x,z));
    }
}

bool comp(pair<pair<int, int>, int> x, pair<pair<int, int>, int> y)
{
    if(x.first.second>y.first.second)
        return 1;
    return 0;
}

inline void Initialization()
{
    mark[1]=1;
    for(int i=0;i<cost[1].size();i++)
        Graf.push_back(make_pair(cost[1][i],1));
    make_heap(Graf.begin(),Graf.end(),comp);
}

void Prim()
{
    Initialization();
    while(!Graf.empty())
    {
        x=Graf[0].second;
        y=Graf[0].first.first;
        z=Graf[0].first.second;
        pop_heap(Graf.begin(),Graf.end(),comp);
        Graf.pop_back();
        if(mark[y]==0)
        {
            mark[y]=1;
            rez=rez+z;
            sol.push_back(make_pair(x,y));
            for(int i=0;i<cost[y].size();i++)
                if(mark[cost[y][i].first]==0)
                {
                    Graf.push_back(make_pair(cost[y][i],y));
                    push_heap(Graf.begin(),Graf.end(),comp);
                }
        }
    }
}

void Write()
{
    printf("%d\n",rez);
    printf("%d\n",N-1);
    for(int i=0;i<sol.size();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();
    Write();
}