#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;
const int NMAX = 200005;
const int inf = 2000;
vector <pair <int,int> > graf[NMAX];
priority_queue <pair<int,int>, vector <pair<int,int> >, greater<pair<int,int> > >coada;
bitset<NMAX> vizitat;
int n,m;
int tatal[NMAX],cost[NMAX];

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

void afisare()
{
    int sum = 0 ;
    for(int i = 1 ; i <= n ; i++)
        sum +=cost[i];
    printf("%d\n%d\n",sum,n-1);
    for(int i = 2 ; i<= n ; i++)
    {
        printf("%d %d\n",i,tatal[i]);
    }
}

void read()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int a,b,c;
    scanf("%d %d",&n,&m);
    for(int i = 0 ; i< m; i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        graf[a].push_back(make_pair(b,c));
        graf[b].push_back(make_pair(a,c));
    }
}


void arborePartial()
{
    coada.push(make_pair(0,1));
    while(!coada.empty())
    {
        int pret = coada.top().first;
        int nod = coada.top().second;
        vizitat[nod] = true;
        coada.pop();
        for(vector <pair<int,int> > :: iterator it = graf[nod].begin() ; it != graf[nod].end() ; it++)
        {
            int vecin = it->first;
            int costvecin = it->second;
            if(vizitat[vecin] == false && cost[vecin] > costvecin)
            {
                coada.push(make_pair(costvecin,vecin));
                tatal[vecin] = nod;
                cost[vecin] =  costvecin;
            }
        }
    }
}

int main()
{
    read();
    preparation();
    arborePartial();
    afisare();
    return 0;
}