#include <cstdio>
#include <queue>
#include <bitset>
#include <vector>
#define Nmax 200005
using namespace std;
bitset <Nmax> vizitat;
vector <pair<int,int> > graf[Nmax];
priority_queue <pair<int,int> , vector<pair<int,int> > , greater< pair<int,int> > >coada;
int n,m;
int tata[Nmax],cost[Nmax];

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

void Prim(int start)
{
    coada.push(make_pair(0,start));
    while(!coada.empty())
    {
        int nod  = coada.top().second;
        if(vizitat[nod] == true)
        {
            coada.pop();
            continue;
        }
        vizitat[nod] = true;
        coada.pop();
        for(vector<pair<int,int> > :: iterator it = graf[nod].begin(); it != graf[nod].end() ; it++)
        {
            if(vizitat[it->second] == 0 && it->first < cost[it->second])
            {
                coada.push(make_pair(it->first,it->second));
                tata[it->second] = nod;
                cost[it->second] = it->first;
            }
        }
    }
}

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



int main()
{
    read();
    Prim(1);
    afisare();
    return 0;
}