#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector<pair<int,int>>graph[200005];
vector<pair<int,int> >rez;
struct d
{
    int from, to, cost;
};

class cmp
{
public:
    bool operator()(d a,d b)
    {
        return a.cost>b.cost;
    }
};

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

int n, m, a, b, c;
bool viz[200005];

void solve()
{
    for (auto &v:graph[1])
        q.push({1,v.first,v.second});
    d sus;
    int cost=0;
    while (!q.empty())
    {
        sus=q.top();
        q.pop();
        if (!viz[sus.to])
        {
            cost+=sus.cost;
            rez.push_back({sus.from,sus.to});
            viz[sus.from]=viz[sus.to]=1;
            for (auto &v:graph[sus.to])
            {
                if (!viz[v.first])
                {
                    q.push({sus.to,v.first,v.second});
                }
            }
        }
    }
    g << cost << '\n';
    g << n-1 << '\n';
    for (auto &v:rez)
        g << v.first <<' ' << v.second << '\n';
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i)
    {
        f >> a >> b >> c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    solve();
    return 0;
}