#include <cstdio>
#include <queue>

using namespace std;

struct edge
{
    int n1;
    int n2;
    int cost;

};

bool operator<(const edge& a, const edge& b)
{
    return a.cost > b.cost;
}

priority_queue<edge> q;
vector<edge> g[200002];
bool vis[200002];
int sol[400002];

void addEdges(int node)
{
    for (int i = 0; i < g[node].size(); i++)
        if (!vis[g[node][i].n2])
            q.push(g[node][i]);
}

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

    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y, c; i <= m; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        edge e;
        e.cost = c;
        e.n1 = x;
        e.n2 = y;
        g[x].push_back(e);
        e.n1 = y;
        e.n2 = x;
        g[y].push_back(e);
    }
    vis[1] = true;
    addEdges(1);

    int cost_min = 0;
    int k = 1;
    edge e;
    while (k <= n && !q.empty())
    {
        e = q.top();
        q.pop();
        if (!vis[e.n2])
        {
            vis[e.n2] = true;
            cost_min += e.cost;
            k++;
            addEdges(e.n2);
            sol[++sol[0]] = e.n1;
            sol[++sol[0]] = e.n2;
        }
    }

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

    return 0;
}