#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <bitset>

#define nMax 200005

using namespace std;

vector < pair<pair<int, int>, int> > v[nMax];
bitset <nMax> viz;
vector< pair<int, int> > sol;
int n, m;

struct cmp
{
    bool operator()(pair<pair<int,int>,int> A, pair<pair<int,int>,int> B)
    {
        return A.second>B.second;
    }
};

priority_queue < pair< pair<int, int>, int>, vector<pair< pair<int, int>, int> >, cmp> q;

void read()
{
    scanf("%d %d\n", &n, &m);
    int x, y, c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d \n", &x, &y, &c);
            v[x].push_back(make_pair(make_pair(x,y),c));
            v[y].push_back(make_pair(make_pair(y,x),c));
    }
}

void prim()
{
    for(int i = 0; i<v[1].size(); ++i)
        q.push(v[1][i]);

    viz[1] = 1;
    int costt = 0;
    while(!q.empty())
    {
        int x = q.top().first.first;
        int y = q.top().first.second;
        int c = q.top().second;
        q.pop();
        if(viz[y] == 0)
        {
            sol.push_back(make_pair(x, y));
            costt += c;
            viz[y] = 1;
            for(int i=0;i<v[y].size();++i)
                if(viz[v[y][i].first.second] == 0)
                    q.push(v[y][i]);
        }
    }

    printf("%d \n", costt);
    printf("%d \n", n-1);

    for(int i=0;i<n-1;++i)
    printf("%d %d\n", sol[i].first, sol[i].second);

}

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

    read();
    prim();
    return 0;
}