#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int sum, nrsol, cost[2005], sol[2005];
vector <pair <int, int> > e[200005];
priority_queue <pair <int, int>, vector<pair <int, int> >, greater<pair <int, int> > > nodes;
bitset <200005> vis;
int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; ++i)
        cost[i] = 1000000137;

    for(int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({b, c});
        e[b].push_back({a, c});
    }

    nodes.push({-1000000137, 1});
    cost[1] = -1000000137;
    vis[1] = true;

    while (!nodes.empty())
    {
        int i = nodes.top().second;
        nodes.pop();

        for(auto it = e[i].begin(); it != e[i].end(); ++it)
        {
            if(sol[i] == it->first)
                continue;

            if(cost[it->first] > it->second)
            {
                if(cost[it->first] != 1000000137)
                    sum -= cost[it->first];
                else ++nrsol;

                sum += it->second;
                sol[it->first] = i;

                cost[it->first] = it->second;

                if(vis[it->first] == false)
                {
                    nodes.push({cost[it->first], it->first});
                    vis[it->first] = true;
                }
            }
        }
    }

    cout << sum << '\n' << nrsol << '\n';

    for(int i = 2; i <= n; ++i)
    {
        cout << sol[i] << ' ' << i << '\n';
    }

    return 0;
}