#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>

#define inf ~(1<<31)

using namespace std;

int n;
vector<pair<int, int> > vec[200010];
int best[200010];
int par[200010];
bitset<200010> done = 0;
int ndone, sum;
vector<pair<int, int> > sol;

struct cmp
{
    bool operator()(int a, int b)
    {
        return best[a] > best[b];
    }
};

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

void citire()
{
    int m, x, y, c;
    scanf("%d%d", &n, &m);
    for(int i = 2; i <= n; i++) best[i] = inf;

    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        vec[x].push_back(make_pair(y, c));
        vec[y].push_back(make_pair(x, c));
    }
}

void adnod(int x)
{
    done[x] = 1;
    ndone++;
    sum += best[x];
    if(par[x])
        sol.push_back(make_pair(par[x], x));

    for(int i = 0; i < vec[x].size(); i++)
        if(!done[vec[x][i].first] && vec[x][i].second < best[vec[x][i].first])
        {
            best[vec[x][i].first] = vec[x][i].second;
            par[vec[x][i].first] = x;
            q.push(vec[x][i].first);
        }
}

void prim()
{
    adnod(1);
    while(!q.empty() && ndone < n)
    {
        if(!done[q.top()])
            adnod(q.top());
        q.pop();
    }
}

void afisare()
{
    printf("%d\n%d\n", sum, sol.size());
    for(int i = 0; i  < sol.size(); i++)
        printf("%d %d\n", sol[i].first, sol[i].second);
}

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

    citire();
    prim();
    afisare();

    return 0;
}