#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#define N 200005
#define inf 1005

using namespace std;

int n,m,cost_min;
int tata[N],cost[N];

vector <pair <int,int> >G[N];

priority_queue <pair <int,int>, vector<pair <int,int> >, greater<pair <int,int> > > pq;

bitset <N> viz;

void prelucrare()
{
    vector <pair<int,int> >::iterator it;

    pq.push(make_pair(0,1));

    tata[1] = 1;
    cost[1] = 0;

    while(!pq.empty())
    {
        int cost_tmp = pq.top().first;
        int nod = pq.top().second;

        pq.pop();

        viz[nod] = true;

        for(it = G[nod].begin(); it != G[nod].end(); ++it)
        {
            if(!viz[it->second] && it->first < cost[it->second])
            {
                pq.push(make_pair(it->first,it->second));

                tata[it->second] = nod;
                cost[it->second] = it->first;
            }
        }
    }
}

int minim()
{
    int s = 0;

    for(int i = 1 ; i <= n ; ++i)
    {
        s += cost[i];
    }
    return s;
}

void umplere()
{
    for(int i = 1 ; i <= n ; ++i)
    {
        cost[i] = inf;
    }
}

void afisare()
{
    printf("%d\n",minim());

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

    for(int i = 2 ; i <= n ; ++i)
    {
        printf("%d %d\n",i,tata[i]);
    }
}

void citire()
{
    scanf("%d %d\n",&n,&m);

    int x,y,c;

    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d %d\n",&x,&y,&c);

        G[x].push_back(make_pair(c,y));
        G[y].push_back(make_pair(c,x));
    }

    umplere();

    prelucrare();

    afisare();
}

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

    citire();

    return 0;
}