#include <bits/stdc++.h>

using namespace std;

#define cin fin
#define cout fout
ifstream fin("apm.in");
ofstream fout("apm.out");

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u, v, cost;
        cin >> u >> v >> cost;
        g[u].push_back({v, cost});
        g[v].push_back({u, cost});
    }
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    vector<int> vis(n + 1);

    vis[1] = 1;
    for (auto [u, cost] : g[1])
    {
        pq.push({cost, 1, u});
    }

    int ans = 0;
    vector<pair<int, int>> sol;

    for (int i = 1; i < n; ++i)
    {
        while (!pq.empty())
        {
            auto [cost, u, v] = pq.top();
            if (vis[v])
            {
                pq.pop();
                continue;
            }
            break;
        }
        if (pq.empty())
        {
            cout << -1 << '\n';
            exit(0);
        }
        auto [cost, u, v] = pq.top();
        vis[v] = true;

        ans += cost;
        sol.push_back({u, v});

        for (auto [u, cost] : g[v])
        {
            pq.push({cost, v, u});
        }
    }

    cout << ans << '\n'
         << n - 1 << '\n';
    for (auto [u, v] : sol)
    {
        cout << u << ' ' << v << '\n';
    }
}