#include<cstdio>
#include<bitset>
#include<queue>
#include<algorithm>

using namespace std;

typedef pair<int,int> PII;
const int NMAX = 200000+5;
const int MMAX = 400000+5;
const int INF = (1LL<<31)-1;

void Read(),Prim(),Print();

int N,M,Sol_cost;
PII E[NMAX];
int Dist[NMAX];
int Dad[NMAX];
bitset<NMAX> Viz;
vector<PII> V[NMAX];
priority_queue<PII,vector<PII>,greater<PII> > PQ;

int main()
{
    Read();
    Prim();
    Print();

    return 0;
}

void Read()
{
    int i,x,y,c;

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d",&N,&M);

    for(i = 1; i <= M; i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        V[x].push_back(make_pair(y,c));
        V[y].push_back(make_pair(x,c));
    }
}

void Prim()
{
    int i,j,x,y,c;
    vector<PII>::iterator it;

    for(i = 2; i <= N; i++)
        Dist[i] = INF;

    Viz[1] = 1;

    for(it = V[1].begin(); it != V[1].end(); it++)
    {
        Dist[it->first] = it->second;
        PQ.push(make_pair(it->second,it->first));
        Dad[it->first] = 1;
    }

    for(j = 0; j < N-1;)
    {
        x = PQ.top().second;
        c = PQ.top().first;
        y = Dad[x];
        PQ.pop();

        if(Viz[x]) continue;

        Viz[x] = 1;

        for(it = V[x].begin(); it != V[x].end(); it++)
            if(Dist[it->first] > it->second)
            {
                Dist[it->first] = it->second;
                PQ.push(make_pair(it->second,it->first));
                Dad[it->first] = x;
            }

        Sol_cost += c;
        E[++j] = make_pair(x,y);
    }
}

void Print()
{
    int i;

    printf("%d\n%d\n",Sol_cost,N-1);

    for(i = 1; i <= N-1; i++)
        printf("%d %d\n",E[i].first,E[i].second);
}