#include <iostream>
#include <stdio.h>
#include <queue>
#include <utility>
#include <vector>
#include <limits.h>

#define pii pair <int,int>
using namespace std;

struct cmp
{

    bool operator()(const pair<pii,int> x,const pair<pii,int> y)
    {
        return x.second>y.second;
    }

};

priority_queue <pair<pii,int>, vector <pair <pii,int> >,cmp> pq;

struct nod
{
    int b;
    int c;
};

vector <nod> g[1000];
vector <pair<pii,int> > sg;
int n, m, cminim=0;
bool v[1000]={0};

void bfs()
{
    pair <pii,int> x;

    int s;

    for(int i=0; i<g[1].size(); i++)
    {
        x.first.first=1;
        x.first.second=g[1][i].b;
        x.second=g[1][i].c;
        pq.push(x);
    }
    v[1]=1;

    while(!(pq.empty()))
   {
        s=pq.top().first.second;
        if(!v[s])
        {
            v[s]=1;
            cminim+=pq.top().second;
            sg.push_back(pq.top());
        }

        pq.pop();

        for(int j=0; j<g[s].size(); j++)
        {
            if(v[g[s][j].b]==0)
            {
                x.first.first=s;
                x.first.second=g[s][j].b;
                x.second=g[s][j].c;
                pq.push(x);
            }
        }

   }
}

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

    int x, y, z;
    nod aux;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d \n", &x, &y, &z);

        aux.b=y;
        aux.c=z;
        g[x].push_back(aux);
        aux.b=x;
        g[y].push_back(aux);
    }

    bfs();
    cout<<cminim<<endl;
    cout<<sg.size()<<endl;

    for(int i=0; i<sg.size(); i++)
        cout<<sg[i].first.first<<" "<<sg[i].first.second<<endl;

    return 0;
}