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

#define INF 999999999

using namespace std;

int n,m,D[400100],sum=0;
bool Vizitat[400100];

struct Solutie {int nod1, nod2;};

Solutie Sol[400100];

vector < pair < int , int > > L[400100];
priority_queue < pair < int , int > > Heap;

void Read()
{
    int a,b,co;
    freopen("apm.in","r",stdin);
    scanf("%i %i",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%i %i %i",&a,&b,&co);
        L[a].push_back({b,co});
        L[b].push_back({a,co});
    }
    for(int i=1;i<=n;i++)
        Vizitat[i] = false;
}

void Prim(int start)
{
    int n1,c1,neigh,n2,c2;
    for(int i=1;i<=n;i++)
        D[i] = INF;
    Heap.push({0,start});
    D[start] = 0;
    Vizitat[start] = true;
    while(!Heap.empty())
    {
        c1 = -Heap.top().first;
        n1 = Heap.top().second;
        Heap.pop();
        Vizitat[n1] = true;
        if(c1 <= D[n1])
        {
            neigh = L[n1].size();
            for(int i=0;i<neigh;i++)
            {
                n2 = L[n1][i].first;
                c2 = L[n1][i].second;
                if(D[n2] > c2 && Vizitat[n2] == false)
                {
                    D[n2] = c2;
                    Heap.push({-D[n2],n2});
                    Sol[n2].nod1 = n1;
                    Sol[n2].nod2 = n2;
                }
            }
        }
    }
}

int main()
{
    freopen("apm.out","w",stdout);
    Read();
    Prim(1);
    for(int i=1;i<=n;i++)
        sum+=D[i];
    printf("%i\n%i\n",sum,n-1);
    for(int i=2;i<=n;i++)
    {
        printf("%i %i\n",Sol[i].nod1,Sol[i].nod2);
    }
    return 0;
}