#include <cstdio>///Varianta lui Prim///
#include <queue>
#include <vector>
#include <bitset>
#define Nmax 200010
#define Inf 2000
using namespace std;
vector < pair <int,int> > graf[Nmax];
priority_queue <pair <int,int> , vector <pair<int,int> > , greater <pair<int,int> > >q;
bitset<Nmax> vizitat;
int n,m;
int tatal[Nmax],cost[Nmax];

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

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

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]);
}

int main()
{
    read();
    arbore_partial();
    afisare();
    return 0;
}